题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1] 输出: 1

示例 2:

输入: [4,1,2,1,2] 输出: 4

题解

无官方题解

这道题目核心在于异或……评论区大佬还是厉害。自己一开始没注意到要求不使用额外空间的要求，只是去用HashSet搞了个线性时间复杂度就算了。

看了一个评论区大佬的题解:感觉除了异或的方法。解法二提到了排序的想法也是可以的：先排序，然后利用两两成对的时候，“索引为偶数时，和后一个配对相等，奇数时与前一个配对相等”的性质，可以进行二分查找。总的来说，排序复杂度O(nlogn），二分查找O（logn），最后复杂度O(nlogn）。虽然没达到题目要求的O(n），但是没有使用额外空间，还是可以的了。

附一下异或的做法：

执行用时 : 1 ms, 在Single Number的Java提交中击败了99.60% 的用户

内存消耗 : 40.6 MB, 在Single Number的Java提交中击败了68.37% 的用户

int ans = nums[0]; if (nums.length > 1) { for (int i = 1; i < nums.length; i++) { ans = ans ^ nums[i]; } } return ans;

算法原理在于，对一个数进行两次同一个数的异或会恢复原来的数。

评论区大佬的题解里面还提到了HashMap的方法，HashMap存次数，跑起来比我的方法还慢一点点。。。应该是HashSet remove比HashMap去遍历get还快。。。但内存消耗比我少就很迷

执行用时 : 28 ms, 在Single Number的Java提交中击败了13.61% 的用户

内存消耗 : 41.5 MB, 在Single Number的Java提交中击败了38.97% 的用户

class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (Integer i : nums) { Integer count = map.get(i); count = count == null ? 1 : ++count; map.put(i, count); } for (Integer i : map.keySet()) { Integer count = map.get(i); if (count == 1) { return i; } } return -1; // can't find it. } }

感想

自己用的HashSet：

执行用时 : 22 ms, 在Single Number的Java提交中击败了19.24% 的用户

内存消耗 : 44 MB, 在Single Number的Java提交中击败了9.02% 的用户

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

set只有一个元素剩下的时候怎么输出都不是很清楚，用了个很蠢的方法。