LeetCode - 136. Single Number(Array, Bit Manipulation)*

문제

비어 있지 않은 정수 숫자의 배열이 주어지면, 하나를 제외한 모든 원소는 두 번 나타난다. 그 싱글을 찾아라. 선형 런타임 복잡성을 가진 솔루션을 구현하고 일정한 추가 공간만 사용해야 합니다.

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

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

풀이

자바입니다.

• HashSet 의 데이터가 중복이 안 되는 특징을 사용해서 풉니다.(중복값은 두 번 만 나타나기 때문에)
• contains() 를 사용해 데이터가 있는지 확인 후 있으면 삭제, 없으면 추가합니다.
• 최종적으로 중복이 안 되는 값 하나만 남습니다.
• iterator().next() 을 사용해서 반환합니다.

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length==1) return nums[0];
        
        Set<Integer> single = new HashSet<>();
        for(int num : nums){
            if(single.contains(num)){
                single.remove(num);
            }else{
                single.add(num);
            }
        }
        return single.iterator().next();
    }
}

• XOR 연산을 사용해서 풉니다.
• ex1) 1,1,0 -> (1^1)^0 -> 0^0 -> 0
  ex2) n1,n1,n,n2,n2 -> (n1^n1)^n^n2^n2 -> (0^n)^n2^n2 -> n^(n2^n2) -> n^0 -> n

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length==1) return nums[0];

        int res = 0;
        for(int num:nums) res^=num;
        return res;
        
    }
}