하나의 숫자가 두 번 나타나는 것을 제외하고 모든 숫자가 세 번 나타나는 정수 배열이 주어지면 두 번 나타나는 숫자를 찾으십니까?

Question

이것은 "프로그래밍 인터뷰의 요소"의 문제입니다. 이 문제는 here으로 게시되었지만 수락 된 답변 (또는 기타 답변)은 완료되지 않았습니다.

기본 3 시스템 (게시물에서 xor3이라고 부름)에서 작동하는 XOR과 비슷한 연산을 사용하면 x xor3 x이라는 결과가 표시됩니다. 그러나 문제는 x입니다. xor3은 모듈러 3의 덧셈으로 정의됩니다 (숫자는 기본 3 시스템으로 표현됩니다)

x xor3 x에서 어떻게 되나요?

Answer 1

숫자 배열을 다시 한번 살펴 본다면 어떻게 될까요? 첫 번째 반복 후에 얻은 값은 a = x xor3 x

이고 배열의 모든 항목을 반복하고 xor3 각각의 값은 a입니다.

for y in arr: 
    if y xor3 a == 0: 
     print y 
     break 
    else 
     continue 

지금은 이것이 순진한 해결책이라고 생각합니다. O (1)을 O (1) 메모리로 사용하여 각각 xor3을 고려하면 여전히 O (n)입니다.