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

Question

题目描述

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

求大神指导最优解法

Answer 1

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

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 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 2

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]

Answer 3

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

如果使用 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 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 4

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
}

Answer 5

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)

Answer 6

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 周年「问答」打卡 ，欢迎正在阅读的你也加入。

Answer 7

简单好理解的去重算法， 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));