一道算法题的题解

一道算法题的题解

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

具体的题目如下:

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

大神的解法

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

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @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
};

简单的分析一下

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

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

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

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

扩展

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

  1. 如果我们要统计出现两次的数字, 其他的不管出现 1 次或者出现 3 次,我们都不需要知道, 那么, 我们返回b就行了.
1
2
3
4
5
6
7
8
9
var singleNumber = function(nums) {
let a = 0,b = 0;
nums.map(n => {
a = a ^ n & ~b
b = b ^ n & ~a
})
- return a
+ return b
};
  1. 如果我们想统计出现 n 次的数字, 那么最简单粗暴的办法就是定义n - 1个变量,也就是我前面所说的全息寄存器. 继续返回第一个就行了.
  2. 同样, 我们在第1 ~ n - 1个寄存器中存储的就是那些出现过1 ~ n - 1次的数字, 当然, 必须要说明的一点是, 这个存储方法是会循环的. 就是, 上面的程序可以返回出现一次的数字信息, 也可以返回出现 4 次的数字信息. 因为 $4\ mod\ 3 = 1$
Author

BorGor

Posted on

2020-04-15

Updated on

2022-01-08

Licensed under

Comments