136. Single Number

136. Single Number

Difficulty: Easy

Given a non-empty 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?

Example 1:

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

Example 2:

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

1.HashSet

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> exists = new HashSet<>();
        for (int i : nums) {
            if (exists.contains(i)) {
                exists.remove(i);
            } else {
                exists.add(i);
            }
        }
        return exists.toArray(new Integer[0])[0];
    }
}

2. xor解法

任何一个数字亦或本身都为0：1 xor 1 = 0，所以假设A为single one：
A ^ B ^ B ^ C ^ C ^ D ^ D ^..... = A

class Solution {
    public int singleNumber(int[] nums) {
        int r = 0;
        for (int i : nums) r ^= i;
        return r;
    }
}