이것에 대한 탐욕적인 접근 방식은 무엇입니까?

Question

우리는 n 배열을 가지고 있습니다.이 배열은 모두 하나만 제외하고이 배열에서 균등하게 반복되었습니다. 우리는 홀수 번 반복되는 번호를 찾고 싶습니다.

나는 최적의 알고리즘이 O(n Log(n))보다 더 복잡하다고 생각한다. 왜냐하면 우리가 배열을 정렬 한 다음 반복 할 수 있고 새로운 수를 볼 수 있기 때문에 누적기를 늘리면 누적기를 감소시키고 누적기를 줄이면 각 누적 기가 0이 아닌 멤버는 홀수 번 반복됩니다.

또한 알고리즘이 O(n)보다 좋지 않다고 생각합니다. 그렇다면 O(Log(n))이어야하고 정렬 된 배열이 필요하지만 초기 배열은 그렇지 않기 때문입니다.

Answer 1

숫자가 정수인 경우 배열의 모든 값을 xor 만 사용할 수 있습니다. 결과는 홀수 회 반복되는 번호입니다 (x에 대해 x xor x = 0이므로 올바른 것입니다). 이 알고리즘의 복잡성은 분명히 O(n)입니다.