本文共 1067 字，大约阅读时间需要 3 分钟。

题目地址：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

题目比较简单，就是一个数组中其他元素都出现过两次，只有一个元素就出现了一次，找出这个元素。

我的思路也很简单，想到了用Java的HashSet，没有的话就填进去，有的话就移出来，反正题目说了，肯定会有一个元素是单个的，所以最后HashSet中肯定会有一个“光棍”剩下来。

下面是Java代码的实现：

public int singleNumber(int[] nums) {    HashSet
   
     set = new HashSet
    
     ();    for (int i = 0; i < nums.length; i++) {        if (!set.contains(nums[i]))            set.add(nums[i]);        else            set.remove(nums[i]);    }    int reslut = 0;    for (Integer t: set) {        reslut = t;    }    return reslut;}
    
   

注意哦，人家题目特意还说了，算法的时间复杂度应该是线性的，而且不要用多余的空间，那意思就是让我们过一遍数据就要得出答案。

在上面的代码中，我们确实也只是过了一遍数据，但是在使用contain和remove方法的时候也花费了时间，所以上面的算法应该比O(n)要大。

因为只有一个是单身，剩下的全是对子，那么我们可以想如果成对的直接抵消不就行了吗，怎么抵消，加减抵消不合适，那么就用位抵消，好，想到这里，按位异或就能上位了。

public int singleNumber(int[] nums) {    int reslut = 0;    for (int t: nums) {        reslut = t ^ reslut;    }    return reslut;}

这段代码比上一个代码简洁了不少，也快了不少。

转载地址：http://akhii.baihongyu.com/