Single Number——寻找数组中仅出现一次的数（Leetcode 136）

代码方法转载自Leetcode 136讨论区。仅供参考分享。

问题描述： Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. 给定一个整数类型的非空数组，每个元素出现次数不是1次就是2次，找到只出现一次的唯一元素。

例子： Example 1:

Input: nums = [2,2,1] Output: 1 Example 2:

Input: nums = [4,1,2,1,2] Output: 4 Example 3:

Input: nums = [1] Output: 1

补充： 1 <= nums.length <= 3 * 104 -3 * 104 <= nums[i] <= 3 * 104 Each element in the array appears twice except for one element which appears only once.

方法： 一.先排列数组再比较

Arrays.sort(nums); for (int i = 0 ; i < nums.length-1 ; i += 2) { if (nums[i] != nums[i+1]) return nums[i]; } // 如果循环结束了都还没有，那肯定是最后一位…… return nums[nums.length-1];

二.利用位运算符的特效 XOR：相同则真，不同则假且取最大值 A XOR A = 0, and A XOR 0 = A 假设有：数组[4,2,1,2,1] 则： 4²1²1 = 4⁽²2)⁽¹1) = 4 ^ (0 ^ 0) = 4 ^ 0 = 4

代码如下：

int a = 0; for (int i = 0;i < nums.length; i++) a ^= nums[i]; return a;

三. This is simply keeping a frequency map.

HashMap<Integer, Integer> map = new HashMap<>(); for (int i=0;i<nums.length;i++) map.put(nums[i], map.getOrDefault(nums[i], 0)+1); for (int key:map.keySet()) if(map.get(key) == 1) return key; return -1;