LeetCode 136 Single Number

题目：

解法：

1. 最容易想到的做法，利用Map记录每个数字出现的次数

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        
        for(int i=0;i<nums.length;i++)
        {
            if(map.containsKey(nums[i])) map.put(nums[i],map.get(nums[i])+1);
            else map.put(nums[i],1);
        }
        for(Integer key: map.keySet())
            if(map.get(key)%2==1)
                return key.intValue();
        return 0;
        
    }
}

2. 利用数学解法，所有不重复的数相加翻倍，则单独的元素会被多加一次，减去数组所有元素和，即可得到单独的元素，要保存不重复的数，需要用到一个hashset

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

  }
}

3. 绝妙的做法，利用异或操作（ ^ ）

　　a ^ 0 = a;

　　a ^ a = 0;

　　a ^ b ^ a = a ^ a ^ b = 0 ^ b = b;

则将数组中的所有数按位异或，就能又快又省空间地得到数组中的单身狗

class Solution {
  public int singleNumber(int[] nums) {

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