O(n) 시간과 O(1) 공간에서 중복 검색
입력: 0 ~n-1의 요소를 포함하는 n개의 요소의 배열이 지정되며, 이러한 숫자 중 하나가 몇 번이라도 표시됩니다.
목표 : O(n)에서 반복되는 숫자를 찾고 일정한 메모리 공간만 사용합니다.
예를 들어 n이 7이고 배열이 {1, 2, 3, 1, 3, 0, 6}이라고 가정하면 답은 1 & 3이어야 합니다.했는데, 요.HashSet★★★★★★★★★★★★★★★.
같은 알고리즘에 대해 효율적인 알고리즘이 있나요?
이것은 추가 부호 비트가 필요 없는 것을 생각해 낸 것입니다.
for i := 0 to n - 1
while A[A[i]] != A[i]
swap(A[i], A[A[i]])
end while
end for
for i := 0 to n - 1
if A[i] != i then
print A[i]
end if
end for
가 순열되므로 요소 " " " " " " " " " " " " " " " " " " " " "x 한 번 존재하는 경우, 중 1이 .A[x].
블러셔에서는 O 않을 수 O(n)는이지만, 「O(n)」로 하고 있는 해 주세요.O(N)은 간이 있는 합니다. 스왑은 다음 메시지가 있는 경우에만 발생합니다.iA[i] != i 요소는 「1」입니다.A[i] == i」(, 「」의 를 의미합니다.while body 'Loop body'입니다.N-1.
두 번째 루프는 다음 값을 출력합니다.x A[x] 않다x첫 루프가 에 - 을 보증합니다 - 음 、 음 、 음 、 음 、 、 - 、x 내에 , 중1개는 「」에 있습니다.A[x]x이치노
cafe의 훌륭한 답변은 배열에 k번 나타나는 각 번호를 k-1번 인쇄합니다.그것은 유용한 행동이지만, 이 질문은 거의 틀림없이 각 복제품을 한 번만 인쇄하도록 요구하며, 그는 선형 시간/정수 공간 한계를 허무는 일 없이 이것을 할 수 있는 가능성을 시사한다.이것은, 2번째 루프를 다음의 의사 코드로 치환하는 것으로 실시할 수 있습니다.
for (i = 0; i < N; ++i) {
if (A[i] != i && A[A[i]] == A[i]) {
print A[i];
A[A[i]] = i;
}
}
은 첫 실행된 후 값 중 가 실행되었을 합니다.m는 여러되며, 그중위치에 있음을 즉, 이 어피아란스는 올바른 위치에 것이 보증합니다.A[m]주의하면, 그 「홈」의 장소를 사용해, 아직 인쇄되지 않았는지 아닌지에 관한 정보를 격납할 수 있습니다.
버전에서는 '네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네, 네.A[i] != i 암시하다A[i]에는 조금 합니다. 즉, 불변수이다.A[i] != i && A[A[i]] == A[i] A[i]는 지금까지 본 적이 없는 복제품입니다.('우리가 이전에 본 적이 없는' 부분을 삭제하면 나머지는 카페의 불변성에 대한 진실과 모든 복제품이 가정 내 위치에 일부 복사가 있음을 보증하는 것으로 간주됩니다.)이 속성은 처음에 유지되며(카페의 첫 번째 루프가 종료된 후), 아래에 각 단계 후에 유지된다는 것을 보여 줍니다.
대해 하면, ★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★A[i] != i테스트의 일부는 을 암시한다A[i] 이전에 볼 수 없었던 복제품일 수도 있어요만약 우리가 그걸 전에 본 적이 없다면, 우리는 예상할 수 있을 것이다.A[i]본고장소입니다.본고장소입니다.이것은, 후반의 시점에서 테스트되고 있는 것입니다.if□□□이 홈 사이클"을 만듭니다.이 경우 인쇄하고 홈 로케이션을 변경하여 처음 발견된 복제를 가리키도록 하여 2단계 "주기"를 만듭니다.
않는 하려면 , 「불변성」이라고 해 주세요.m = A[i] 포지션에 iA[i] != i && A[A[i]] == A[i]변화(는A[A[i]] = i은, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 보다, 합니다.m 하기 .if만, 「실패할 수 있다 「실패할 수 없다」라고 하는 경우에 요.i 로케이션에 합니다.m네, 그럴 겁니다. 왜냐면 、 록록록이도도도i은요, 첫 번째 은요.if 「」입니다.A[i] != i2부에서는, 그것이 가리키는 장소가 자택의 장소인지 아닌지를 테스트하고, 그 장소가 자택이 아닌지를 확인합니다.이 상황에서, 우리는 더 이상 그 여부를 알 수 없다.m ★★★★★★★★★★★★★★★★★」A[m]는 중복된 값이지만, 어느 쪽이든 이미 보고된 것을 알 수 있습니다.이는 이 2사이클이 카페의 첫 번째 루프의 결과에는 나타나지 않음을 보증하기 때문입니다.(이 경우 주의해 주십시오.m != A[m] 정확히 쪽인가.m ★★★★★★★★★★★★★★★★★」A[m]는 여러 번 발생하고 다른 하나는 전혀 발생하지 않습니다.)
여기 의사 코드가 있습니다.
for i <- 0 to n-1:
if (A[abs(A[i])]) >= 0 :
(A[abs(A[i])]) = -(A[abs(A[i])])
else
print i
end for
이 배열을 단방향 그래프 데이터 구조로 표시한다고 가정합니다. 각 숫자는 정점이고 배열의 인덱스는 그래프의 가장자리를 형성하는 다른 정점을 가리킵니다.
보다 단순하게 하기 위해 지수 0 ~ n-1과 0 . n ~ 1 범위의 숫자 범위를 가지고 있다.
0 1 2 3 4
a[3, 2, 4, 3, 1]
0(3) --> 3(3)은 사이클입니다.
답변: 인덱스에 의존하여 어레이를 이동하기만 하면 됩니다.a[x] = a[y]이면 순환이므로 중복됩니다.다음 인덱스로 건너뛰고 배열이 끝날 때까지 계속 진행합니다.복잡도: O(n) 시간과 O(1) 공간.
비교적 작은 N의 경우 div/mod 연산을 사용할 수 있습니다.
n.times do |i|
e = a[i]%n
a[e] += n
end
n.times do |i|
count = a[i]/n
puts i if count > 1
end
C/C++는 아니지만 어쨌든
어레이가 너무 크지 않으면 이 솔루션이 더 단순해집니다.따라서 같은 크기의 다른 어레이를 만듭니다.
1 입력 어레이와 같은 크기의 비트맵/어레이를 만듭니다.
int check_list[SIZE_OF_INPUT];
for(n elements in checklist)
check_list[i]=0; //initialize to zero
2 입력 어레이를 스캔하여 상기 어레이의 수를 늘립니다.
for(i=0;i<n;i++) // every element in input array
{
check_list[a[i]]++; //increment its count
}
3 이제 check_list 어레이를 스캔하여 중복된 횟수를 1회 또는 여러 번 인쇄합니다.
for(i=0;i<n;i++)
{
if(check_list[i]>1) // appeared as duplicate
{
printf(" ",i);
}
}
물론 위의 솔루션에서 소비되는 공간의 2배가 소요되지만 시간 효율은 O(2n)로 기본적으로 O(n)입니다.
C의 솔루션은 다음과 같습니다.
#include <stdio.h>
int finddup(int *arr,int len)
{
int i;
printf("Duplicate Elements ::");
for(i = 0; i < len; i++)
{
if(arr[abs(arr[i])] > 0)
arr[abs(arr[i])] = -arr[abs(arr[i])];
else if(arr[abs(arr[i])] == 0)
{
arr[abs(arr[i])] = - len ;
}
else
printf("%d ", abs(arr[i]));
}
}
int main()
{
int arr1[]={0,1,1,2,2,0,2,0,0,5};
finddup(arr1,sizeof(arr1)/sizeof(arr1[0]));
return 0;
}
O(n) 시간과 O(1) 공간의 복잡성입니다.
알고리즘은 다음 C 함수에서 쉽게 확인할 수 있습니다.원래 어레이를 취득하는 것은 필수는 아니지만 각 엔트리 모듈을 취득할 수 있습니다.
void print_repeats(unsigned a[], unsigned n)
{
unsigned i, _2n = 2*n;
for(i = 0; i < n; ++i) if(a[a[i] % n] < _2n) a[a[i] % n] += n;
for(i = 0; i < n; ++i) if(a[i] >= _2n) printf("%u ", i);
putchar('\n');
}
테스트용 Ideone 링크.
static void findrepeat()
{
int[] arr = new int[7] {0,2,1,0,0,4,4};
for (int i = 0; i < arr.Length; i++)
{
if (i != arr[i])
{
if (arr[i] == arr[arr[i]])
{
Console.WriteLine(arr[i] + "!!!");
}
int t = arr[i];
arr[i] = arr[arr[i]];
arr[t] = t;
}
}
for (int j = 0; j < arr.Length; j++)
{
Console.Write(arr[j] + " ");
}
Console.WriteLine();
for (int j = 0; j < arr.Length; j++)
{
if (j == arr[j])
{
arr[j] = 1;
}
else
{
arr[arr[j]]++;
arr[j] = 0;
}
}
for (int j = 0; j < arr.Length; j++)
{
Console.Write(arr[j] + " ");
}
Console.WriteLine();
}
private static void printRepeating(int arr[], int size) {
int i = 0;
int j = 1;
while (i < (size - 1)) {
if (arr[i] == arr[j]) {
System.out.println(arr[i] + " repeated at index " + j);
j = size;
}
j++;
if (j >= (size - 1)) {
i++;
j = i + 1;
}
}
}
별로 예쁘지는 않지만 적어도 O(N)와 O(1) 속성을 쉽게 볼 수 있습니다.기본적으로 어레이를 스캔하여 각 번호에 대해 대응하는 위치에 플래그가 이미 1회(N) 또는 이미 여러 번(N+1) 설정되어 있는지 확인합니다.이미 1회 플래그가 붙어 있는 경우는, 인쇄해, 이미 여러 번 플래그를 붙입니다.플래그가 지정되지 않은 경우 이미 한번 플래그를 지정하고 대응하는 인덱스의 원래 값을 현재 위치로 이동합니다(플래그는 파괴적인 작업입니다).
for (i=0; i<a.length; i++) {
value = a[i];
if (value >= N)
continue;
if (a[value] == N) {
a[value] = N+1;
print value;
} else if (a[value] < N) {
if (value > i)
a[i--] = a[value];
a[value] = N;
}
}
또는 (더블 루프에도 불구하고) 더 나은 방법:
for (i=0; i<a.length; i++) {
value = a[i];
while (value < N) {
if (a[value] == N) {
a[value] = N+1;
print value;
value = N;
} else if (a[value] < N) {
newvalue = value > i ? a[value] : N;
a[value] = N;
value = newvalue;
}
}
}
자세한 내용은 https://youtu.be/qJ_Y7pKP0e4를 참조하십시오.
코드는 이쪽 https://github.com/TechieExpress/DataStructures/blob/main/findDuplicates
코드 조각:
/**
*
* @author techieExpress
*
* You are given a list of n-1 integers and these integers are in the range * of 1 to n.
* Input: Given an array of n elements which contains elements
* from 0 to n-1, with any of these numbers appearing any number of times.
*
* Goal: To find these repeating numbers in O(n) and using only constant * * memory space.
**/
public class findDuplicates {
public static void main(String args[])
{
int arr[] = { 2,1,1,2 };
for (int i = 0; i < arr.length; i++) {
arr[arr[i] % arr.length]
= arr[arr[i] % arr.length]
+ arr.length;
}
System.out.println("The repeating elements are : ");
for (int i = 0; i < arr.length; i++) {
//System.out.print(numRay[i]);
if (arr[i] >= arr.length * 2) {
System.out.println(i + " ");
arr[i]=arr[i]%arr.length;
}
}
}
}
다음을 통해 O(n) 시간과 O(1) 공간의 복잡성을 수행할 수 있습니다.
ith 어레이 요소를 사용합니다.
마이너스일 경우 +ve로 합니다.
마지막으로 배열 색인(ith 요소)에서 가져온 숫자에 -1을 곱합니다.
양수인 경우 인덱스를 반환합니다.
def findDuplicate(self, arr: List[int]) -> int: n=len(arr) for i in range(0,n): arr[(abs(arr[i]))-1]=arr[(abs(arr[i]))-1]*(-1) if arr[(abs(arr[i]))-1]>0: return abs(arr[i])
언급URL : https://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space
'programing' 카테고리의 다른 글
| VueJ - 동적 데이터로 URL 업데이트 (0) | 2022.07.17 |
|---|---|
| 중복되는 사용자 아이콘 생성 (0) | 2022.07.17 |
| "Interpolation inside attribute is removed"를 해결하려면 어떻게 해야 합니까?v-bind 또는 colon sermark를 사용하시겠습니까?"Vue.js 2 (0) | 2022.07.17 |
| Java 8에서 Lamda를 사용하여 Map을 다른 Map으로 변환하려면 어떻게 해야 합니까? (0) | 2022.07.17 |
| C/C++ 런타임 라이브러리와 C/C++ 표준 라이브러리의 차이점 (0) | 2022.07.17 |