js面试题：取出数组中出现两次的值

Question

输入一个长度为n的数组a，其中有的数据出现一次有的出现两次，返回其中出现两次的数据

不开辟额外空间，时间复杂度O(n)

如输入［1, 1, 2, 3, 5, 3］返回 ［1, 3］

Answer 1

看了一下，最好的是 @madRain 的解法。
然后又仔细读了下题。要求只找出出现过两次的项。在此题中还有一个已知的限定条件，重复的项最多只会出现2次。所以 @madRain 的解法是最优的。如果没有这个已知项，那是无论如何也无法在O(n)中判断出的，当找出重复项时并不知道后续是否还有重复项，只有在有顺序的数组中才能在一次中完成判断，所以至少要O(2n)。而正因为此题有了这个限定条件，所以可以实现O(n)

---

要O(n)就只能一次遍历，而且还不能开辟额外空间，即既不能另外做一个缓存列表，也无法使用新的数组。在这种情况下，是无法完成的。
不过，O(n)不行，O(2n)却是可以的。第一步先对数组排序，第二步再比较前后项即可。

const arr = [1, 1, 2, 3, 5, 3];

for (let i = arr.sort().length - 1; 0 < i; i -= 1) {
  i -= arr.splice(i, 1)[0] === arr[i - 1];
}

console.log(arr);

Answer 2

数组中重复的数据

Answer 3

这道题像是力扣 260 的变体，可以借鉴其解题思路。
而力扣260传播最广的解法是用 BitMap缓存遍历进度，用亦或运算的特性a^a===0来判定数据出现偶数次。这里判定之后，再用&运算获取判定结果。
在 ES2020- 的环境中需要用 ArrayBuffer + DataView 来实现 Bitmap，现在可以用 BigInt来糊弄：

function detect(arr){
    let spaceLength = 0; // 用来标记数组里作为结果的空间有多长
    let bitMap = BigInt(2 ** arr[0]);  // BitMap
    for(let i = 1; i < arr.length; i++){
        const item = arr[i];
        const itemLength = BigInt(2 ** item);
        
        // 如果对应的 bit 有偶数次重复的话，经过亦或就变成了0
        bitMap ^= itemLength; 
        if(!(bitMap & itemLength)){
            // 把结果写回数组，“避免开辟新的空间”
            arr[spaceLength] = item
            spaceLength++
        }
    }

    // splice 的时间复杂度有待商榷，据说在 V8 是[1, O(n)]区间
    arr.splice(spaceLength);
    
    // 另一种方法，直接修改数组 length，复杂度我没研究过
    // arr.length = space Length;
    
    return arr
}

由于用了 BigInt，可能导致效率低下。

Answer 4

“不开辟额外空间”大意是指不使用新的堆内存吧，不然 @madRain 也用不着在答案里用那么拧巴的 BigInt 来搞什么 BitMap 了。
既然不能使用新的堆内存，那你们这些额外用数组、对象缓存中间值的岂不是一个个都犯规了？
要我说，JS 的数组有很多特点：它是不定长的、它本身作为对象可以用字符串索引、它可以像C一样使用负数索引而且不用担心内存越界……但凡善用这里的任意一个“优势”，也不至于一个个对“不开辟额外空间”这几个大字选择性失明。

Answer 5

var findDuplicates = function(nums) {
    const res = [];
    for (const num of nums) {
        const absNum = Math.abs(num);
        if (nums[absNum - 1] < 0) {
            res.push(absNum);
        } else {
            nums[absNum - 1] = -1 * nums[absNum - 1];
        }
    }

    return res;
};

Answer 6

O(n) 的没想到，O(m + n) 的有一个：

const arr = [1, 1, 2, 3, 5, 3]
let obj = {};
arr.forEach(_ => {
  if (obj[_]) {
    obj[_]++
  } else {
    obj[_] = 1
  }
})
let res = []
Object.keys(obj).forEach(_ => {
  if(obj[_] === 2) {
    res.push(Number(_))
  }
})

Answer 7

我难道是个假前端，怎么感觉大家都会，什么变体，什么O(n),我完全没概念 :(

Answer 8

除非限定一些条件，否则O(2n)都不一定有，限定的条件有2条,此外还需要保证最多只有2个重复（这就是力扣中国442问题）

1. a[i]>=1
2. a[i]<=N

其中N是数组元素数
此外还需要允许计数器变量之类的

function findD(a){
    let N=a.length;
    let rt=[];
    for(let i=0;i<N;i++){
        if(a[i]>0){
            if(a[a[i]-1]<0) rt.push(a[i]);
            a[a[i]-1]=-1*a[a[i]-1];
        }else{
            if(a[-1*a[i]-1]<0) rt.push(-1*a[i]);
            a[-1*a[i]-1]=-1*a[-1*a[i]-1];
        }
    }
    return rt;
}

上面的算法就是一个O(n)的算法啦。