[LeetCode - Data Structure II] 136. Single Number

Problem

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.

Solution

반복되지 않고 한 번만 나오는 숫자를 찾는 문제다.

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]);
            }
        }
        
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            return iterator.next();
        }
        return 0;
    }
}

(1) HashSet에 중복이 안 되는 것은 add, 중복이면 remove로 set 세팅
(2) 마지막에 Iterator로 최종 출력

---

제출하고 다른 사람들의 답을 확인해 보니 Iterator을 제외하고 다른 방법으로 출력을 하는 코드를 발견했다. 

 1) stream을 이용한 방법

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.stream().findFirst().get();
    }
}

 2) 더 빠르고 좋은 코드 (비트 연산자 사용)

class Solution {
    public int singleNumber(int[] nums) {
        int value = 0;
        for(int i = 0; i < nums.length; i++){
            value ^= nums[i];
        }
        
        return value;
    }
}

결론

비트 연산자에 대한 공부를 해봐야겠다!!!

Reference

https://leetcode.com/problems/single-number/