[c++] O (n) 시간 및 O (1) 공간에서 중복 찾기

caf의 훌륭한 대답 은 배열에 k 번 나타나는 각 숫자를 k-1 번 인쇄합니다. 이것은 유용한 동작이지만 질문은 각 복제물이 한 번만 인쇄되도록 요구하며 선형 시간 / 상수 공간 경계를 날리지 않고이를 수행 할 수있는 가능성을 암시합니다. 이것은 그의 두 번째 루프를 다음 의사 코드로 대체하여 수행 할 수 있습니다.

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]. 주의를 기울이면 해당 “홈”위치를 사용하여 사본이 아직 인쇄되었는지 여부에 대한 정보를 저장할 수 있습니다.

caf의 버전에서 배열을 살펴 A[i] != i보았을 때 그것이 A[i]중복 임을 암시했습니다 . 내 버전에서는 약간 다른 불변에 의존합니다. A[i] != i && A[A[i]] == A[i]이는 이전에 본 적이없는A[i] 중복 임을 의미합니다 . ( “우리가 이전에 본 적이없는”부분을 삭제하면 나머지는 caf의 불변의 진실과 모든 복제본이 홈 위치에 일부 사본이 있다는 보장에 의해 암시되는 것으로 볼 수 있습니다.)이 속성은 다음과 같습니다. 처음 (카페의 첫 번째 루프가 끝난 후)와 각 단계 후에 유지된다는 것을 아래에 보여줍니다.

배열을 살펴보면 A[i] != i테스트 부분의 성공은 이전에 본 적이없는 중복 일 A[i] 수 있음을 의미합니다 . 이전에 본 적이 없다면 A[i]의 집 위치가 자신을 가리킬 것으로 예상 if합니다. 이것이 조건의 후반부에서 테스트 한 것입니다. 이 경우 인쇄하고 홈 위치를 변경하여 처음 발견 된이 복제본을 다시 가리 키도록하여 2 단계 “주기”를 만듭니다.

이 작업은 우리의 불변을 변경할 생각하지 않는 것을 확인하려면 m = A[i]특정 위치에 대한 i만족 A[i] != i && A[A[i]] == A[i]. 우리가 만든 변경 사항 ( A[A[i]] = i)은 조건의 m후반부 if를 실패하게하여 다른 집이 아닌 항목이 중복으로 출력되는 것을 방지하기 위해 작동 하지만 i, 집 위치에 도착하면 작동 m할까요? 예, 이제이 새로운 조건 i에서 if조건의 전반부 A[i] != i가 참인 것을 발견 하더라도 후반부는 가리키는 위치가 집 위치인지 아닌지 여부를 테스트하기 때문입니다. 이 상황에서 우리는 더 이상 여부를 알 수 없습니다 m또는 A[m]중복 값이었다, 그러나 우리는 어느 쪽이든 것을 알고,이 2주기가 caf의 첫 번째 루프의 결과에 나타나지 않도록 보장되기 때문에 이미보고되었습니다 . ( m != A[m]그런 다음 정확히 하나의 mand 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

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

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;
    }
  }
}

#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;
}

   0  1  2  3  4
 a[3, 2, 4, 3, 1]