[algorithm] Find the only Non-Duplicate Element in Array

주어진 배열(N: 2n+1)에서 단 1개만 중복(쌍을 가지지 않는)되지 않는 요소라고 할때

본 요소를 찾는 방법으로 일반적으로 정렬 (오름차순이던 내림차순이던) 후 linear 하게 순차적으로 요소를 비교 하여 값 추출 하는 방법을 생각 할 수 있습니다.

func searchNonDuplicateElement(A : [Int]) -> Int {

  var sorted = A.sorted()

  var idx = 0

  while (true) {

    if sorted.count - 1 != idx {

      if sorted[idx] == sorted[idx + 1] {

        idx += 2

      } else {

        return sorted[idx]

      }

    } else {

      return sorted[idx]

    }

  }

}

먼저 배열을 정렬 한 다음 순차적으로 비교해 가면서 중복되지 않는 요소를 찾으며  O (n log n) 시간 복잡도가 발생합니다.

좀 더 효과적인 방법은 없을까요? 바로 XOR를 사용 하는 방법입니다.

func EnhanceSearchNonDuplicateElement(A: [Int]) -> Int {

  var result = 0

  _ = A.map { result ^= $0 }

  

  return result

}

각 Element 들을 XOR 한다고 가정하면, 결과적으로 중복되지 않는 요소만 남을 것입니다.

이는 O(n) 이나 O(n log n) 의 시간복잡도가 발생합니다.