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中的另外一个数字。