목록에서 단일 숫자 찾기

StackOverflow https://stackoverflow.com/questions/35185

  •  09-06-2019
  •  | 
  •  

문제

이 질문에는 이미 답변이 있습니다.

다른 모든 숫자가 정확히 두 번 발생하는 목록에서 한 번만 발생하는 숫자를 찾는 가장 좋은 알고리즘은 무엇입니까?

따라서 정수 목록(배열로 사용)에서 각 정수는 하나만 제외하고 정확히 두 번 반복됩니다.그것을 찾으려면 가장 좋은 알고리즘은 무엇입니까?

도움이 되었습니까?

해결책

가장 빠르고(O(n)) 메모리 효율적인(O(1)) 방법은 XOR 연산을 사용하는 것입니다.

C에서:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

그러면 한 번만 발생하는 "1"이 인쇄됩니다.

이것은 처음으로 숫자를 쳤을 때 num 변수 자체를 표시하고 두 번째에는 num 자체를 표시 해제하기 때문에 작동합니다(다소).표시되지 않은 유일한 것은 중복되지 않은 것입니다.

다른 팁

그런데 이 아이디어를 확장하면 매우 빠르게 찾을 수 있습니다. 둘 중복 목록 중 고유 번호입니다.

고유번호를 a와 b라고 부르자.먼저 Kyle이 제안한 대로 모든 것의 XOR을 수행합니다.우리가 얻는 것은 a^b입니다.a != b이기 때문에 우리는 a^b != 0을 알고 있습니다.a^b의 1비트를 선택하고 이를 마스크로 사용합니다. 자세한 내용은 다음과 같습니다.x & (a^b)가 0이 아니도록 x를 2의 거듭제곱으로 선택합니다.

이제 목록을 두 개의 하위 목록으로 나눕니다. 하나의 하위 목록에는 y&x == 0인 모든 숫자 y가 포함되고 나머지는 다른 하위 목록에 들어갑니다.그런데 x를 선택하면 a와 b가 서로 다른 버킷에 있다는 것을 알 수 있습니다.또한 각 복제본 쌍이 여전히 동일한 버킷에 있다는 것도 알고 있습니다.이제 우리는 오래된 "XOR-em-all" 트릭을 각 버킷에 독립적으로 적용하고 a와 b가 무엇인지 완전히 알아낼 수 있습니다.

빵.

O(N) 시간, O(N) 메모리

HT= 해시 테이블

ht.clear ()가 보이는 각 항목에 대해 목록을 넘어갑니다.

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

결국 HT에 있는 항목이 귀하가 찾고 있는 항목입니다.

참고(크레딧 @Jared Updike):이 시스템은 아이템의 모든 이상한 인스턴스를 찾습니다.

논평:사람들이 NLogN 성능을 제공하는 솔루션에 어떻게 투표할 수 있는지 모르겠습니다.어느 우주에서 그게 "더 나은"가요?나는 당신이 허용된 답변의 NLogN 솔루션을 표시했다는 사실에 더욱 충격을 받았습니다...

그러나 메모리가 일정해야 한다면 NLogN이 (지금까지는) 최선의 솔루션이 될 것이라는 점에는 동의합니다.

Kyle의 솔루션은 데이터 세트가 규칙을 따르지 않는 상황을 포착하지 못할 것입니다.모든 숫자가 쌍으로 구성된 경우 알고리즘은 0이라는 결과를 제공하며, 0과 정확히 동일한 값이 단일 발생의 유일한 값이 됩니다.

단일 발생 값이나 삼중 발생 값이 여러 개 있는 경우에도 결과는 오류입니다.

데이터 세트 테스트는 메모리나 시간 측면에서 더 많은 비용이 드는 알고리즘으로 끝날 수도 있습니다.

Csmba의 솔루션은 일부 오류 데이터(단일 발생 값이 하나 이상)를 표시하지만 다른 데이터(사중)는 표시하지 않습니다.그의 솔루션과 관련하여 HT 구현에 따라 메모리 및/또는 시간은 O(n)보다 큽니다.

입력 세트의 정확성을 확신할 수 없는 경우 정수 자체가 해시 키인 경우 정렬 및 계산 또는 해시 테이블 계산 발생을 사용하는 것이 모두 가능합니다.

정렬 알고리즘을 사용한 다음 정렬된 목록을 통해 숫자를 찾는 것이 좋은 방법이라고 말하고 싶습니다.

이제 문제는 "최고의" 정렬 알고리즘을 찾는 것입니다.많은 정렬 알고리즘이 있으며 각 알고리즘에는 장점과 단점이 있으므로 이는 상당히 복잡한 질문입니다.그만큼 위키피디아 항목 그것에 대한 좋은 정보 소스인 것 같습니다.

Ruby로 구현:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

"최고"가 무엇을 의미하는지 지정해야 합니다. 어떤 사람에게는 속도가 가장 중요하며 "최고"라고 답할 자격이 있는 사람도 있습니다. 다른 사람에게는 솔루션의 가독성이 더 좋으면 몇 백 밀리초도 용서할 수 있습니다.

"최고"는 더 구체적이지 않는 한 주관적입니다.

그것은 말했다:

숫자를 반복하면서 각 숫자에 대해 해당 숫자에 대한 목록을 검색하고 검색 결과 수에 대해 1만 반환하는 숫자에 도달하면 작업이 완료됩니다.

당신이 할 수 있는 최선의 방법은 목록을 반복하는 것입니다. 모든 항목에 대해 "본" 항목 목록에 추가하거나 이미 있는 경우 "본" 항목에서 제거하고 마지막에는 "본" 목록을 제거하는 것입니다. " 항목에는 단일 요소가 포함됩니다.이는 시간 측면에서 O(n)이고 공간 측면에서 n입니다(최악의 경우 목록을 정렬하면 훨씬 더 좋아질 것입니다).

그것들이 정수라는 사실은 실제로 고려되지 않습니다. 왜냐하면 그것들을 더하는 것으로 할 수 있는 특별한 일이 없기 때문입니다...거기 있어요?

질문

선택한 답변이 어떤 기준에서든 "최고"인 이유를 이해할 수 없습니다.O(N*lgN) > O(N), 목록을 변경합니다(또는 목록의 복사본을 생성하므로 공간과 시간 면에서 여전히 더 비쌉니다).뭔가 빠졌나요?

숫자가 얼마나 큰지/작은지/다양한지에 따라 다릅니다.O(N log N) 솔루션의 정렬 시간을 크게 줄이는 기수 정렬을 적용할 수 있습니다.

정렬 방법과 XOR 방법은 시간 복잡도가 동일합니다.두 문자열의 비트별 XOR이 상수 시간 연산이라고 가정하는 경우 XOR 방법은 O(n)뿐입니다.이는 배열의 정수 크기가 상수로 제한된다는 것과 같습니다.이 경우 Radix 정렬을 사용하여 O(n)으로 배열을 정렬할 수 있습니다.

숫자에 제한이 없으면 비트별 XOR은 O(k) 시간이 걸립니다. 여기서 k는 비트 문자열의 길이이고 XOR 방법은 O(nk)를 사용합니다.이제 다시 기수 정렬은 O(nk) 시간에 배열을 정렬합니다.

충돌이 발견될 때까지 세트의 요소를 해시에 간단히 넣을 수 있습니다.루비에서 이것은 한 줄짜리입니다.

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

그래서, find_dupe([1,2,3,4,5,1]) 1을 반환합니다.

하지만 이것은 실제로 일반적인 "트릭" 인터뷰 질문입니다.일반적으로 하나의 중복이 있는 연속 정수 목록에 관한 것입니다.이 경우 면접관은 종종 가우스 합을 사용하기 위해 당신을 찾고 있습니다. N-정수 트릭. n*(n+1)/2 실제 금액에서 차감됩니다.교과서의 대답은 이렇습니다. 

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top