비트 연산자를 사용하여 배열에 한 번만 존재하는 숫자 찾기

Question

두 번 발생하는 숫자가 포함 된 배열이 있고 한 번만 발생하는 숫자가있는 경우 XOR 연산자를 사용하여 공산 법. 예컨대

1 2 3 2 3 
1^2^3^2^3 = (2^2)^(3^3)^1 = 1 

그러나 우리는 다른 숫자가 시간을 발생 시킬수 N 수 있습니다 때 한 번 배열에 occures 수를 찾기 위해 비트 트릭을 사용할 수 있습니다, N> 1?

Answer 1

비트 연산자를 사용하면 n이 항상 짝수가 아니라면 안됩니다.

그러나 한 번 발생하는 항목에 대한 정렬 및 스캔 또는 입력 도메인이 어떻게 든 제한되면 각 항목을 버킷에 할당하는 등의 다른 방법을 사용할 수 있습니다. 그것은 (예를 들어) 하나의 숫자 음이 아닌 정수에 한정있어 가정 초

def findASingle(list): 
    if list length is zero: 
     return nothing 
    if list length is one: 
     return first item in list 
    sort list 
    for each item in last other than first and last: 
     if item is different to both previous and next item: 
      return item 

그리고, : :는 제의 예로서

는

def findASingle(list): 
    create count[0..9], all set to zero 
    for each item in last: 
     count[item] = count[item] + 1 
    for each index 0 through 9 inclusive: 
     if count[index] is 1: 
      return index 
    return nothing 

Answer 2

는 방법이 이진 연산자가 아닌 그렇게 할 수 있습니다. 각 숫자를 비트 벡터로 표시 한 다음 sum (mod n)을 사용하여 모든 벡터를 합계 할 수 있습니다. 결과 벡터는 고유 번호를 나타냅니다.

예

, 이제 고려해 보자 N = 3 및 서열 2 3 5 2 5 5 2

벡터는 : [0 1 0], [0 1 1], [1 0 1], [0 1 0], [1 0 1], [1 0 1], [0 1 0]

당 요소 합의 모든 벡터는 다음과 같습니다 : [3 4 4]

Mod 3 : [0 1 1]은 3 - 고유 요소에 해당합니다.

이것은 XOR 트릭의 일반화입니다. 실제로 XOR은 mod 2에서의 합산입니다.