Problem
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.Example 2:
Input: nums = [-1,0] Output: [-1,0]Example 3:
Input: nums = [0,1] Output: [1,0]Constraints:
・ 2 <= nums.length <= 3 * 10⁴ ・ -2³¹ <= nums[i] <= 2³¹ - 1 ・ Each integer in nums will appear twice, only two integers will appear once.
Idea
Set을 이용해서 간단하게 풀 수도 있지만, time complexity는 O(n), space complexity는 O(c)로 풀어야 한다는 제약 사항이 있다. 이런 문제는 bitwise연산을 사용하거나 주어진 nums의 공간을 이용해야 한다. 문제를 파악해보면 두 수를 제외하면 같은 값을 가진 수가 쌍으로 있다는 조건이 있다. 같은 수의 경우 특이사항은 XOR 연산을 하면 0이 나온다는 것이다. 즉, 이 문제는 bitwise 연산을 이용해 풀 수가 있다.
전체 수를 bitwise 연산하면 같은 값이 없는 두 수 a와 b를 xor 연산한 값이 나온다.
x = a ^ b
위 조건을 만족하는 a와 b의 경우의 수는 너무나 많다. 따라서 주어진 수를 모아놓은 array를 다시 활용해야 한다.
a와 b는 같은 값이 아니기 때문에 x에서 1인 bit가 반드시 존재한다. 그렇다면 nums에서 서로 다른 bit를 가진 수로 나누면 되지 않을까? 두 수만 분리하면 나머지 수는 쌍으로 존재하는 값이기 때문에 xor 연산을 통해 제거할 수 있다.
즉, array를 다시 탐색하는 대신 1인 bit값을 기준으로 나누어 xor 연산을 수행한다. array를 전부 탐색하면서 xor 연산을 수행한 두 개의 값이 우리가 원하는 a와 b가 되는 것이다.
실제론 혼자 못 풀어서 문제를 푼 다른 블로그를 참조했다. Reference를 보면 설명이 잘 되어있으니 참조!
Solution
class Solution {
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
int xor = 0;
for (int num : nums) {
xor ^= num;
}
int bit = 0;
for (int i=0; i < 32; i++) {
if ((xor >>> i & 1)!= 0) {
bit = i;
break;
}
}
int seperator = 1 << bit;
for (int num : nums) {
if ((seperator & num) == 0) {
res[0] ^= num;
continue;
}
res[1] ^= num;
}
return res;
}
}Reference
https://leetcode.com/problems/single-number-iii/
http://yucoding.blogspot.com/2016/12/leetcode-question-single-number-iii.html
