编写一个js算法,用一次循环将数组中出现2次或者以上的值删掉

题目描述

var arr = [1, 2, 4, 1, 5, 5];
最终返回:[2, 4]

自己的CODE

const removeDuplicates = (newArr) => {
  const obj = {};
  for (let i = 0; i >= 0 && i < newArr.length; i += 1) {
    if (newArr[i] in obj) {
      newArr.slice(obj[newArr[i]], 1);
      newArr.splice(i, 1);
      i -= 2;
    }
    obj[newArr[i]] = i;
  }
  console.log(" result: ", newArr);
};

removeDuplicates(arr);

求大神指导最优解法

回复
阅读 2.6k
7 个回答

补充:之前理解错题目了,以为是去重,看了其他人的回答发现是只要有重复就都去掉,重答一下:

var removeDuplicates = (newArr) => {
  const obj = {};
  for (let i = 0; i < newArr.length;i++) {
        const value = newArr[i];
    if (value in obj) {
            newArr[i] = null;
            typeof obj[value] === 'number' && (newArr[obj[value]] = null);
            obj[value] = true;
    } else obj[value] = i;
  }
  console.log(" result: ", newArr.filter(v => v !== null));
};
removeDuplicates([1, 2, 4, 1, 5, 5]);

时间复杂度O(2n),空间复杂度O(n)


感觉你的思路可能是对的,但是看代码又好像没完全对,给你优化下

const removeDuplicates = (newArr) => {
  const obj = {};
  const result = []
  for (let i = 0; i < newArr.length; i += 1) {
    if (newArr[i] in obj) {
      continue
    }
    result.push(newArr[i])
    obj[newArr[i]] = 1
  }
  console.log(" result: ", result);
};

removeDuplicates([1, 2, 4, 1, 5, 5]);
已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ,欢迎正在阅读的你也加入。
const arr=[1,2,4,1,5,5]; 
const newArr = arr.filter(function(item) {
  return arr.lastIndexOf(item) == arr.indexOf(item);
});
console.log(newArr)  //[2,4]

一开始并不想回答这个问题,因为我没找到“一次”循环解决问题的办法。@我才不乱来 的办法已经很不错了,看起来也只用了一次循环。但实际上 indexOflastIndexOf 也是循环实现的。

如果使用 Hash Set 或者 Hash Map 是可以在一定程度上避免循环的(也不能完全避免,底层处理冲撞会用到)但问题在于,建立 Hash 表的过程本身就得用一个循环来实现。

这么来考虑:当你找到一个元素的时候,并不知道它是不是会出现第二次,如果你先当作唯一,保存起来,那发现第二次的时候,就一定得去结果数组里把它删掉,查找过程是一个新的循环;如果先当不唯一,标记次数,那结束后需要去把所有不唯一的组合起来成新数组,这个过程是遍历过滤,也需要循环实现。

当然可能还有一个比较复杂一点的办法 —— 回溯,也就是往后检查到有异,再回过头去重新处理。这样看起来似乎只需要一个循环,不过肯定会有多次往返,实际是在一条循环链上反复跑,处理起比较复杂。

const unique = (arr) => {
    const map = {};
    const result = [];

    for (let i = 0; i < arr.length; i++) {
        const v = arr[i];

        // 标记对象,count 是计数,根据下面的逻辑,并不是准确计数,只计 1 或者大于 1(即2)
        // si 表示该值在原数组中第一次出现的 index,
        // ri 表示该值在结果数组中的 index
        // 这里代表表示,如果没做标记,就先标记,并取出来;如果已经做过,直接取出来。
        const mark = map[v] ??= { si: i, ri: result.length, count: 1 };

        // 如果当前元素已经出现过多次,直接跳过
        if (mark.count > 1) { continue; }

        // 如果当前元素是就是源数组中首次出现的元素,而且 count === 1(上面已经处理过大于 1 的情况),
        // 那么只需要直接添加到结果数组中即可。
        if (i === mark.si) {
            result.push(v);
            continue;
        }

        // 初始值就是 1,所以这里加了后肯定大于 1
        mark.count++;

        // 由于标记大于 1,找到它第 1 次出现的位置,把 i 回溯过去
        // 因为本次循环体结束会 i++,所以要 -1
        i = mark.si - 1;
        // 重置 result 长度,把后面的结果都丢掉,从那个元素开始重新处理后面的
        result.length = mark.ri;
    }

    return result;
};

const arr = [1, 2, 4, 1, 5, 5];
console.log(unique(arr));

此外,还有一种办法,不使用循环,使用递归 —— 有回溯处理通常会用到递归。


function check(result, arr, i, map = {}) {
    // 递归出口
    if (i >= arr.length) { return; }

    const v = arr[i];

    // 还是加标记对象,并累加当前元素的记数
    const mark = (map[v] ??= { count: 0 });
    mark.count++;

    // 继续向后统计,统计结束再来做判断
    check(result, arr, i + 1, map);

    // 统计完成,仍然只有 1,那就加到结果集中
    // mark 是个对象引用,后面统计会更新 count,但不会产生新对象,
    // 所以前端取的引用仍然有效
    if (mark.count === 1) {
        result.unshift(v);
    }
}

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

const result = [];
check(result, arr, 0);
console.log(result);

对了,补充一下,对题主代码的分析

直接修正好像有点困难,参考我上面的第一种处理方法,我猜题主是想用那种回溯的方法来处理。另外就是请 @高健 注意两个问题(注释中也写了)

  1. 逻辑上应该保证 i >= 0,而不是把它作为循环结束条件。如果确实存在 i < 0 时需要结束循环,由于不是正常结束条件,一般也是写在循环体中,达到异常结束条件时用 break 来结束。
  2. i += 1 可以直接写成 i++ 或者 ++i。如果考虑性能,自增指令会比加法运算再赋值更快(当然在这么高级的语言中不一定能体现出来这个效率差)。
const removeDuplicates = (newArr) => {
    const obj = {};
    // 下面有 i -= 2 的操作,所以需要判断 i >= 0,
    // 但问题是,逻辑上应该保证在 i += 1 之后(下次进入循环体前)是有效的,也就是不应该小于 0。
    // 所以这里应该只需要判断 i < newArr.length。
    // 顺便,i += 1 可以直接写成 i++ 或者 ++i。
    for (let i = 0; i >= 0 && i < newArr.length; i += 1) {
        if (newArr[i] in obj) {
            // 这个 slice 的结果没被保存,也没使用,也不会产生副作用,所以这句话没必要啊
            newArr.slice(obj[newArr[i]], 1);
            console.log("before", i, newArr);

            // 检查到已经存在,删除掉,然后呢?
            newArr.splice(i, 1);

            // 这里回到上上个元素是什么意思?
            // 比如在 i === 3 的时候,发现值 1 重复,把这个 1 删掉报
            // i 回到 1 (3-2),指向 2。下次处理因为有 i += 1,所以指向 4
            // 但这时候再处理 4 发现 4 已经存在于 map 中,会被删掉……这就错了。
            // 而且即使回溯,也应该回溯到第 0 个元素,也就是值 1 那里,不应该回溯一个固定长度。
            i -= 2;
        }
        obj[newArr[i]] = i;
    }
    console.log(" result: ", newArr);
};

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ,欢迎正在阅读的你也加入。
  1. 你的code和你的文字题目不符啊,你处理掉的是偶数个重复值,[1,1,2,4,1]会不会被处理成[2]?
  2. 你说的做一次循环,是指对计算复杂度还是心智复杂度?我怀疑你并不是在出算法题,而是寻求代码中for含量最低的封装。

其人的答案都非常好了,我也没啥新意。顺着你的思路写个按位的排除法。

function AA(arr:number[]){
    let newarr = 0
    let repeat = 0
    for (let q of arr){
        let item = 1 << (q-1)
        if ((repeat & item) == item )
            continue;
        if ((newarr & item) == item ){
            newarr = newarr ^ item
            repeat = repeat | item
        }else{
            newarr = newarr | item
        }
    }
    let slot = 1
    let out = []
    while (newarr>0) {
        if ((newarr & 1)==1){
            out.push(slot)
        }
        slot++;
        newarr = newarr >> 1
    }
    return out
}
function removeDuplicates(arr) {
  const once = new Set(), multiple = new Set();
  for (const x of arr) {
    if (multiple.has(x)) continue; // x 之前出现过多次,跳过
    if (once.delete(x)) { // x 之前出现过一次,删除并移入 multiple
      multiple.add(x);
    } else { // x 之前没有出现,移入 once
      once.add(x);
    }
  }
  return [...once];
}

console.log(removeDuplicates([1, 2, 4, 1, 5, 5])) // [2, 4]
console.log(removeDuplicates([4, 4, 2, 3, 2, 1, 2, 0, 0])) // [3, 1]

时间复杂度:O(n)
空间复杂度:O(n)

const removeDuplicates = arr => {
  const map = new Map();
  for(const num of arr){
      let count = map.get(num) || 0;
      count++;
      // count为元素出现的次数
      map.set(num,count);
  }
  return [...map.entries()].filter(([k,v]) => v === 1).map(([k,v]) => k);
}
console.log(removeDuplicates([1, 2, 4, 1, 5, 5]));

参考答案

时间复杂度为O(4n)省略常数O(n),空间复杂度同样算下来也是O(n)。

已参与了 SegmentFault 思否社区 10 周年「问答」打卡 ,欢迎正在阅读的你也加入。

简单好理解的去重算法, O(n)线性复杂度;

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

const removeDuplicates = (arr) => {
    const map = new Map(), res = [];
    for (const v of arr) {
        if (!map.get(v)) map.set(v, 0);
        map.set(v, map.get(v) + 1);
    }
    for( const [k,v] of map.entries()){
        if( v === 1 ) res.push(k);
    }
    return res;
}

console.log(removeDuplicates(arr));
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
宣传栏