LeetCode 136. Single Number [Easy]

发表于 更新于 分类于 ， 阅读次数：

题目来源：https://leetcode.com/problems/single-number/

题目难度：Easy

解答1[Java]：

1
2
3
4
5
class Solution {
    public int singleNumber(int[] nums) {
        
    }
}

思路

  • If we take XOR of zero and some bit, it will return that bit
    • $a \oplus 0 = a$
  • If we take XOR of two same bits, it will return 0
    • $a \oplus a = 0$
  • $a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b$

So we can XOR all bits together to find the unique number.

本题拓展

有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。

示例 :

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

题目再解析

根据前面找一个不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果。

然后，因为这两个只出现一次的元素一定是不相同的，所以这两个元素的二进制形式肯定至少有某一位是不同的，即一个为 0 ，另一个为 1 ，现在需要找到这一位。

根据异或的性质 任何一个数字异或它自己都等于 0，得到这个数字二进制形式中任意一个为 1 的位都是我们要找的那一位。

再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。

  • 将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个
  • 将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。

这样就解出题目。忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。

来源：有哪些解决完之后让你拍案叫绝的算法问题？

核心思想

两个数不一样，肯定至少有一个二进制位是不一样的。我们就从不一样的二进制位中选择一个。设这两个数为A 和 B。

现在假设我们已经选择了某一个二进制位，假设我们选择的是从右向左数第2位，简称第2位。

因为除了这两个数之外其他的数都是成对出现的，所以其他的数中，第2位是0的数是成对出现的，第2位是1的数也是成对出现的。

而A和B的第2位，只有两种可能：

（1）A的第2位是1，B的第2位是0；

（2）A的第2位是0，B的第2位是1。

所以，如果我们把第2位为0的所有数都相互之间做异或运算，必然能够找出A和B中的一个数字，因为其他的数都是成对出现的，异或之后所有位都0了。

再把第2位为1的所有数都相互之间做异或运算，必然能够找出A和B中的另外一个数字。