136. Single Number

문제

---

Single Number - LeetCode

​

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with

a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1] Output: 1

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Example 3:

Input: nums = [1] Output: 1

 

Constraints:

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

Each element in the array appears twice except for one element which appears only once.

​

---

내 풀이

class Solution {
	public int singleNumber(int[] nums) { 
    	HashSet<Integer> set = new HashSet<>(); 
        for (int i=0; i<nums.length; i++) { 
        	if (set.contains(nums[i])) { 
            	set.remove(nums[i]); 
            } else { 
            set.add(nums[i]); 
            } 
         } 
         return set.iterator().next(); 
     } 
}

Runtime

12ms

Memory

44.68MB

​

풀이는 다음과 같다

​

nums 내 모든 원소 선형 탐색

set 내에 존재하지 않으면 추가, 존재하면 제거

선형 탐색이 끝난 후 마지막으로 남아있는 원소 return

​

---

 

참고할 만한 풀이

class Solution { 
	public int singleNumber(int[] nums) { 
    	return xor(0,nums); 
    } 
    public int xor(int n,int[] nums) { 
		if(n>=nums.length) 
        	return 0; 
        return nums[n]^xor(n+1,nums); 
    } 
}

 

XOR 을 사용한 풀이

​

xor의 성질은 다음과 같다.

1. a XOR a = 0

2. a XOR 0 = a

3. a XOR b = b XOR a

​

즉, [1,2,3,4,3,2,1]이라는 배열을 가지고 xor 연산을 하게 되면

1 xor 2 xor 3 xor 4 xor 3 xor 2 xor 1

= 1 xor 1 xor 2 xor 2 xor 3 xor 3 xor 4 (3번 성질)

= (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor 4 (1번 성질)

= 0 xor 0 xor 0 xor 4 (2번 성질)

= 4

​

따라서 갯수가 홀수인 값만 남게 된다.