136. Single Number

136. Single Number
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

题解

第一种：将数据存到一个list中，相同的就remove掉

class Solution {
    public int singleNumber(int[] nums) {
        List<Integer> no_duplicate_list = new ArrayList();
        
        for (int i : nums) {
            if (no_duplicate_list.contains(i)) {
                no_duplicate_list.remove(new Integer(i));
                continue;
            }
            
            no_duplicate_list.add(i);
            
        }
        
        return no_duplicate_list.get(0);
        
    }
}

复杂度分析

时间复杂度：O(n^2)O(n 2) 。我们遍历 ext{nums}nums 花费 O(n)O(n) 的时间。我们还要在列表中遍历判断是否存在这个数字，花费 O(n)O(n) 的时间，所以总循环时间为 O(n^2)O(n 2) 。
空间复杂度：O(n)O(n) 。我们需要一个大小为 nn 的列表保存所有的 ext{nums}nums 中元素。

第二种：用map，还是一样，有的删除，没有的put

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> no_duplicate_map = new HashMap<>();
        
        for (int i : nums) {
            
            if (null == no_duplicate_map.get(i)) {
                no_duplicate_map.put(i, 1);
                continue;
            }
           
            no_duplicate_map.remove(i);
            
        }
        
        for (int i : nums) {
            if (no_duplicate_map.get(i) != null && no_duplicate_map.get(i) == 1) {
                return i;
            }
            
            continue;
            
        }
        
        return 0;
        
    }
}

第三种：2∗(a+b+c)−(a+a+b+b+c)=c

这种仅仅适用于本题目，只有最多只会出现两次，最少出现一次，且出现一次的只能有一个这种情况

class Solution {
    public int singleNumber(int[] nums) {
       int sumOfSet = 0;
        int sumOfNums = 0;
        Set<Integer> set = new HashSet<>();
        
        for (int i : nums){
            if (!set.contains(i)) {
                set.add(i);
                sumOfSet += i;
            }
            
            sumOfNums += i;
        }
        
        return 2 * sumOfSet - sumOfNums;
        
    }
}

第四种：异或

如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位
a⊕0=a
如果我们对相同的二进制位做 XOR 运算，返回的结果是 0
a⊕a=0
XOR 满足交换律和结合律
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

天呐，这都是些什么人

都是神仙嘛？

怎么能想出来的。。。

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