一道算法题的题解

今天看到了一道算法题, 并不是这道算法题有多困难或者优秀,而是某位大神给出的答案,真的是让人眼前一亮.不得不写一下.

具体的题目如下:

题目链接:面试题 56 - II. 数组中数字出现的次数 II

大神的解法

原版是 Java 版本的,我已经改成了 JavaScript 版本.

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
    let a = 0, b = 0;
    nums.map(n => {
      a = a ^ n & ~b
      b = b ^ n & ~a
    })
    return a
  };

简单的分析一下

代码中你的变量a和b相当于两个全息寄存器, 为何说是寄存器呢? 因为每当有一个数字经过a和b的处理之后,他们都会在其中留下痕迹,
下次可以检测到.

具体代码执行的过程其实比较简单.

1. 当n第一次经过循环: 将n的信息保存到了a中.
2. 当n第二次经过循环: 将n的信息转移到b中.
3. 当n第三次经过循环: 将n的信息的逆, 转移到a中, 这样的话,其实就是相当于将n的信息从a中抹去了.

最终得到的a就只剩下了只出现过一次的数字信息了.

扩展

这种解法其实是可以扩展的, 比如说:

1. 如果我们要统计出现两次的数字, 其他的不管出现 1 次或者出现 3 次,我们都不需要知道, 那么, 我们返回b就行了.

var singleNumber = function(nums) {
    let a = 0,b = 0;
    nums.map(n => {
        a = a ^ n & ~b
        b = b ^ n & ~a
    })
-   return a
+   return b
};

2. 如果我们想统计出现 n 次的数字, 那么最简单粗暴的办法就是定义n - 1个变量,也就是我前面所说的全息寄存器. 继续返回第一个就行了.
3. 同样, 我们在第1 ~ n - 1个寄存器中存储的就是那些出现过1 ~ n - 1次的数字, 当然, 必须要说明的一点是, 这个存储方法是会循环的.
   就是, 上面的程序可以返回出现一次的数字信息, 也可以返回出现 4 次的数字信息. 因为 $4\ mod\ 3 = 1$