(알고리즘) 중복된 값에서 UniqueInteger만 뽑기
여러개의 숫자가 있다.
예를들어 3 8 2 8 2 3 1
즉, 1을 제외한 나머지 숫자들은 2번씩 중복된다. 이때 1의 값을 찾아라
풀) 해쉬맵 사용 그러나 복잡도가 O(n) , 그러나 O(1)으로 가능하다.
XOR이용
XOR특성
1 7 9를 XOR하면 1 7 9의 성분이 남아있다
그러나 여기서 다시 7을 XOR하면 1 9만 남는다.
즉 이런식으로 0의 값을 다 하게 되면 마지막에 유니크 Integer 값만 남는다.
예를들어 3 8 2 8 2 3 1
즉, 1을 제외한 나머지 숫자들은 2번씩 중복된다. 이때 1의 값을 찾아라
풀) 해쉬맵 사용 그러나 복잡도가 O(n) , 그러나 O(1)으로 가능하다.
XOR이용
XOR특성
1 7 9를 XOR하면 1 7 9의 성분이 남아있다
그러나 여기서 다시 7을 XOR하면 1 9만 남는다.
즉 이런식으로 0의 값을 다 하게 되면 마지막에 유니크 Integer 값만 남는다.
댓글
댓글 쓰기