只出现一次的数字

本文转载自：https://blog.csdn.net/biezhihua/article/details/79571917

题目

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注：

你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗？

解法1

使用Hash表，建立一个元素 - 出现次数的映射关系，然后再遍历一遍数组找出出现次数唯一的元素。

public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer value = map.get(nums[i]); map.put(nums[i], (value == null ? 0 : value) + 1); } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { return entry.getKey(); } } return 0; }

解法2

在解题时应该充分考虑题目所给的条件。

比如“给定一个整数数组，除了某个元素外其余元素均出现两次”，我们由此可以知道，若该数组有序，且有一个元素只出现一次，以步数2向后遍历，那么一定会存在a[i] != a[i+1]。

public int singleNumber1(int[] nums) { Arrays.sort(nums); for (int i = 0; i < nums.length ; i = i + 2) { if (i + 1 >= nums.length ) { return nums[i]; } if (nums[i] != nums[i + 1]) { return nums[i]; } } return -1; }

解法3

除了上面两个较为普通的解法，还有一个比较不容易想到的解法。

根据计算机基础可以知道：

& 两者同时为真才为真

0010 0100 & 0010 0100 = 0010 0100

由以上可得知，相同数字做&运算，会得到相同的数字。

| 两者一者为真就为真

0010 0100 | 0010 0100 = 0010 0100

由以上可得知，相同数字做|运算，会得到相同的数字。

^ 相同为假，不同为真

0010 0100 ^ 0010 0100 = 0000 0000

由以上可得知，相同数字做^异或运算，会得到0。

由此延伸到题目中，可以得知，若存在一个数字只出现一次，那么该数组所有元素异或结果大于0.

下面是代码。从这个例子中可以知道优秀算法与普通算法之间巨大的性能差异。这也是算法思维在面试中必考的原因之一。

public int singleNumber2(int[] nums) { int res = 0; for (int i : nums) { res ^= i; } return res; }