LeetCode Study : 136. Single Number

問題

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

Example 1:

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

Example 2:

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

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

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

自分の解答

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (set.contains(num)) {
            set.remove(num);
        } else {
            set.add(num);
        }
    }
    return set.stream().findFirst().get();
}

コード理解

別解

public int AsingleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result = result ^ num;
    }
    return result;
}

Time : / Space :

出たわ〜　ビット演算きたわ〜〜　きっついな〜〜

^はXOR演算子で、「同じなら0、違うなら1を返す」です。つまり

0 0 -> 0
0 1 -> 1
1 0 -> 1
1 1 -> 0

で、例えば 2,1,1,3,2やと

10
01
01
11
10

でXORをとると結局 11 でちゃんと3　が導かれると。 わかるかい！！ｗｗｗｗ

今後のための考え方

• 同じ数かどうかはXORで判断できるし、その対象となる数が多くても、どんな順番でも重複の判断が可能