[LeetCode] 136. Single Number - 문제풀이

Description

비어있지 않은 배열이 주어지고 하나의 원소만 한개의 값을 가지고 나머지는 2개씩 값을 가지고있을때 하나의 원소 반환하는 문제입니다.

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 * 10^4
• -3 * 10^4 <= nums[i] <= 3 * 10^4
• Each element in the array appears twice except for one element which appears only once.

Solution 1. 비트연산 - XOR

public int singleNumber(int[] nums) {

    // 1. xor
    int len = nums.length;
    if(len == 1) return nums[0];

    for (int i = 1; i < len ; i++) {
        nums[i] = nums[i-1]^nums[i];
    }

    return nums[len-1];
}

비트가 같으면 0, 다르면 1이 되는 XOR 연산을 통해 쌍이 아닌 값을 뽑아 낼 수 있습니다.

((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5.

Solution 2. Hash Table

public int singleNumber2(int[] nums) {
    // 2. hash table
    int len = nums.length;
    Map<Integer,Integer> map = new HashMap<>(); // value, count
    for (int i = 0; i < len ; i++) {
        map.put(nums[i], map.getOrDefault(nums[i],0)+1);
    }
    for(Integer key : map.keySet()){
        if(map.get(key) == 1){
            return key;
        }
    }
    return -1;
}

hash table을 이용해서 value별 count를 기록하고 1개만 있는 값을 반환합니다.

Reference

Single Number - LeetCode