136. Single Number

- 원문

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

- 해석

정수 배열을 감안할 때 모든 요소는 하나만 제외하고 두 번 나타납니다. 그 하나를 찾아라.

노트:

알고리즘의 선형 런타임 복잡성이 있어야합니다. 여분의 메모리를 사용하지 않고 구현할 수 있습니까?

- 회고

이 문제를 처음 봤을 때 leetcode 문제 중 448. Find All Numbers Disappeared in an Array 문제와 같은 유형의 문제라고 생각했다. 하지만 448번 문제의 경우에는 1번이라도 나온 경우에 음수로 만드는 것이고, 이 문제는 2번 나왔는지를 체크해야하기 때문에 다른 방식으로 접근해야한다. 그 중에서 비트연산을 이용한 해결책을 봤는데 가장 심플한 해결책이라고 생각해 소개하고자 한다.

- 소스코드

public class Solution {
    public int singleNumber(int[] nums) {
        
        int ans =0;    
	int len = nums.length;
	
        for(int i = 0; i < len ;i++){
	    ans ^= nums[i];
	    System.out.println(i + " " + ans);
	}
	    
	return ans;
    }
}

- Logic

이 문제를 해결하기 위해 bitwise XOR을 사용합니다.  먼저 자바에서 비트 XOR을 알아야합니다.   0 ^ N = N  N ^ N = 0   따라서 ..... N이 단일 숫자 인 경우     N1 → N1 → N2 → N2 → ... → Nx → Nx → N   = (N1 ^ N1) ^ (N2 ^ N2) ^ .............. ^ (Nx ^ Nx) ^ N   = 0 ^ 0 ^ .......... ^ 0 ^ N   = N 의 방식으로 구할 수 있습니다.

문제를 풀다보니 비트연산의 특징을 이용한 문제를 많이 보게되어서, 나중에 따로 이에 관련된 내용을 포스팅하도록 하겠다.