No136只出现1次的数字

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

image.png
image.png

使用计数器

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

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次的数字:

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再减去原来数组的和。

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和任何数异或等于任何数本身:

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
image.png

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

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

4 ^ 1 ^ 4 ^ 6 => 1 ^ 6

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

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

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

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

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

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

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];
};