H5W3
当前位置:H5W3 > 其他技术问题 > 正文

【Web前端问题】js面试题:取出数组中出现两次的值

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

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

如输入[1, 1, 2, 3, 5, 3]返回 [1, 3]

回答:

看了一下,最好的是 @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);

回答:

数组中重复的数据

回答:

这道题像是力扣 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,可能导致效率低下。

回答:

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

回答:

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

回答:

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(_))
  }
})

回答:

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

回答:

除非限定一些条件,否则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)的算法啦。

本文地址:H5W3 » 【Web前端问题】js面试题:取出数组中出现两次的值

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址