LeetCode笔记：136. Single Number

问题：

Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

大意：

给出一个整数数组，其中每个元素都出现了两次，只有一个出现一次。找到这个只出现一次的数字。 注意： 你的算法应该有一个线性的时间复杂度。能不能不用额外的内存来实现它？

思路：

我能想到的最直接的思路就是先排序然后从头到尾比较后找出那个唯一的数字，但是这种思路很简单粗暴，感觉一定不是出题人想要的答案，而且并不太能满足注意事项，但想不出别的我只能先这样实现了，然后我看了看别人的高级做法顿时觉得思路清奇实在是精妙无比。

先说排序的做法，直接使用Java的排序函数对数组进行排序，然后从头到尾进行比较，注意要考虑只有一个数字的极端情况，以及单个数字在数组头或者数组尾的情况，还有就是在比较时你会发现，数组排序后，这个数字绝对不可能出现在第二位或者倒数第二位，因为这样的话第一位或者最后一位数字就尴尬了。对于中间的一串数字无非就是进行循环比较了，很无脑。

代码（Java）：

public class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        if (nums.length == 1) return nums[0];
        if (nums[0] != nums[1]) return nums[0];
        if (nums[nums.length-2] != nums[nums.length-1]) return nums[nums.length-1];
        for (int i = 1; i < nums.length-3;i++) {
            if (nums[i] != nums[i+1] && nums[i+1] != nums[i+2]) {
                return nums[i+1];
            }
        }
        return 0;
    }
}

他山之石：

重点来了，我们来看看高手是怎么做的：

// java:
public int singleNumber(int[] nums) {
        int result = 0;
        for(int i=0;i<nums.length;i++) result ^= nums[i];
        return result;
}

四行代码就解决了，我们看看它做了什么，先设定一个0，然后循环和数组中的每个数去做异或运算，每次得出的结果都继续和下一个数再异或。最后得出来的结果就是单个的那个数了！为什么？我演算了一下希望找到规律，发现确实如此。因为异或这个运算有三个很重要的特性：

• 两个相同的数异或后为0；
• 0和一个数异或后为那个数；
• 异或运算满足交换律。

那么我们用0去依次和数组中的数进行异或，结果再继续和下一个数异或，一遍下来，每个数字都异或到了，交换律一遍，就是让每两个相同的数字都自己跟自己异或，结果都是0，然后0和那个单独的数字异或，结果就是那个单独的数字！拍案叫绝！

// C++:
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        auto iter = nums.begin();
        while (iter != nums.end()) {
            res = res ^ *iter;
            iter++;
        }
        return res;
    }
};

查看作者首页