No136只出现1次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

image.png

使用计数器

比较朴素的解法是对每个元素进行计数，最后统计出数量为1的那个数，这种算法比较通用，可以解决任意多元素出现任意次，因为可以解决的问题比较多，所以往往不是最好的算法，需要维护一个HashMap，占用O(N)的空间：

1
2
3
4
5
6
7
8
9
10
11
12
var singleNumber = function (nums) {
  const counter = new Map();
  for (const num of nums) {
    let count = counter.get(num) || 0;
    counter.set(num, ++count);
  }
  for (const [k, v] of counter) {
    if (v === 1) {
      return k;
    }
  }
};

使用Set

事实上我们也不需要真的用HashMap维护一下元素的数量，因为题目提高只有一个元素只有1个，别的元素都有两个，可以使用Set来巧妙处理：当第一次需要该数字的时候将其放进set，第二次遇到的时候将其移除，这样下来set中保存的就是只出现1次的数字：

1
2
3
4
5
6
7
8
9
10
11
var singleNumber = function (nums) {
    const set = new Set();
    for (const num of nums) {
        if (set.has(num)) {
            set.delete(num);
        } else {
            set.add(num);
        }
    }
    return [...set][0];
};

使用数学计算

其基本数学公式是：2*(a+b+c) - (a + a + b + b + c) = c,我们只需要对原数组去重后求和乘以2再减去原来数组的和。

1
2
3
4
var singleNumber = function (nums) {
    // 数学法:2*(a+b+c) - (a  + a + b + b + c)  = c
    return 2 * sum([...new Set(nums)]) - sum(nums);
};

异或运算

这是这道题效率最高也是最让人惊艳的解法，它基于这样一个事实:a ^ a = 0,a ^ a ^ b = a ^ b ^ a = b，异或运算满足交换律，两个相同的数异或结果为0，0和任何数异或等于任何数本身：

1
2
3
4
5
6
7
8
var singleNumber = function (nums) {
    // 位操作：异或法
    let result = 0;
    for (const num of nums) {
        result = result ^ num;
    }
    return result;
};

面试题56-1

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

image.png

和上道题一样，解法1和解法2也同样可以解决这道题，题目要求空间复杂度为O(1)，也就是不能使用额外的空间，能不能也使用位运算这种骚操作来解决呢？我在评论区找到了一个非常精美的答案：

由于数组中存在着两个数字不重复的情况，我们将所有的数字异或操作起来，最终得到的结果是这两个数字的异或结果：(相同的两个数字相互异或，值为0)) 最后结果一定不为0，因为有两个数字不重复。

1
2
3
4
5
4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

6 对应的二进制： 110
1 对应的二进制： 001
1 ^ 6  二进制： 111

此时我们无法通过 111（二进制），去获得 110 和 001。那么当我们可以把数组分为两组进行异或，那么就可以知道是哪两个数字不同了。我们可以想一下如何分组：

  • 重复的数字进行分组，很简单，只需要有一个统一的规则，就可以把相同的数字分到同一组了。例如：奇偶分组。因为重复的数字，数值都是一样的，所以一定会分到同一组！
  • 此时的难点在于，对两个不同数字的分组。此时我们要找到一个操作，让两个数字进行这个操作后，分为两组。我们最容易想到的就是& 1操作， 当我们对奇偶分组时，容易地想到& 1，即用于判断最后一位二进制是否为1。来辨别奇偶。

你看，通过&运算来判断一位数字不同即可分为两组，那么我们随便两个不同的数字至少也有一位不同吧！我们只需要找出那位不同的数字mask，即可完成分组（& mask）操作。为了操作方便，我们只去找最低位的mask:

1
2
3
num1: 101110    110     1111
num2: 111110    001     1001
mask: 010000    001     0010

由于两个数异或的结果就是两个数数位不同结果的直观表现，所以我们可以通过异或后的结果去找最低位的mask！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var singleNumbers = function (nums) {

    // 将所有数进行亦或得到的结果就是那两个不同数的结果 1^4^4^6 = 1^6
    let k = 0;
    for (const num of nums) {
        k ^= num;
    }

    // 获得k中最低位的1
    // mask = k & (-k) 这种方法也可以得到mask（树状数组的lowbit函数），具体原因百度 哈哈哈哈哈
    let mask = 1;
    while ((k & mask) === 0) {
        mask <<= 1;
    }

    let a = 0, b = 0;
    for (const num of nums) {
        if ((num & mask) === 0) {
            a ^= num;
        } else {
            b ^= num;
        }
    }

    return [a, b];
};