数组去重的几种方法

在 JavaScript 中,数组去重是一个常见的需求。下面我们来探讨几种常用的数组去重方法。

双重 for 循环

使用双重 for 循环是一种比较直观的数组去重方法。外层循环遍历原数组的每个元素,内层循环检查该元素是否已经存在于新数组中,如果不存在就添加到新数组。

function uniqueArray(arr) {
  let result = [];

  for (let i = 0; i < arr.length; i++) {
    let isDuplicate = false;
    for (let j = 0; j < result.length; j++) {
      if (arr[i] === result[j]) {
        isDuplicate = true;
        break;
      }
    }
    if (!isDuplicate) {
      result.push(arr[i]);
    }
  }

  return result;
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

这种方法虽然直观,但时间复杂度较高,为 O(n^2)。当数组长度较大时,效率会比较低。

filter + indexOf

利用 filter 方法和 indexOf 方法也可以实现数组去重。filter 会遍历数组的每个元素,对于每个元素,判断它在原数组中第一次出现的位置是否等于当前位置,如果是则保留,否则过滤掉。

function uniqueArray(arr) {
  return arr.filter((item, index) => arr.indexOf(item) === index);
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

这种方法简洁易懂,时间复杂度为 O(n)。

forEach + includes

使用 forEach 遍历原数组,对于每个元素,用 includes 判断它是否已经存在于新数组中,如果不存在就添加进去。

function uniqueArray(arr) {
  let result = [];

  arr.forEach((item) => {
    if (!result.includes(item)) {
      result.push(item);
    }
  });

  return result;
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

这种方法和使用 indexOf 类似,时间复杂度也是 O(n)。

先 sort 再遍历

先对原数组进行排序,这样相同的元素就会被排在一起。然后遍历排序后的数组,把不重复的元素放入新数组中。

function uniqueArray(arr) {
  arr.sort();
  let result = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] !== arr[i + 1]) {
      result.push(arr[i]);
    }
  }

  return result;
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

这种方法的时间复杂度取决于排序算法,如果使用快速排序,平均时间复杂度为 O(nlogn)。

另一种写法是将当前元素与结果数组的最后一个元素比较:

function uniqueArray(arr) {
  arr.sort();
  let result = [];

  for (let item of arr) {
    if (item !== result[result.length - 1]) {
      result.push(item);
    }
  }

  return result;
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

sort + reduce

先对原数组进行排序,再利用 reduce 方法遍历数组,把不重复的元素累加到结果数组中。

function uniqueArray(arr) {
  arr.sort();

  return arr.reduce((prev, cur) => {
    if (cur !== prev[prev.length - 1]) {
      prev.push(cur);
    }
    return prev;
  }, []);
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

这种方法将遍历和结果累加放在一起,代码简洁,时间复杂度与先 sort 再遍历一致。

Set

利用 ES6 新增的 Set 数据结构也可以很方便地实现数组去重。Set 可以保证内部元素的唯一性。

function uniqueArray(arr) {
  return [...new Set(arr)];
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

将数组传入 Set 构造函数中,就可以得到一个去重后的 Set 对象。再利用扩展运算符将 Set 转为数组即可。

这种方法代码最简洁,时间复杂度为 O(n)。

Object 键值对

利用 Object 的键值对特性也可以实现数组去重。将数组元素作为 Object 的键,值设为任意。由于 Object 的键不能重复,所以最终得到的就是一个去重后的对象。

function uniqueArray(arr) {
  let obj = {};

  arr.forEach((item) => {
    obj[item] = 0;
  });

  return Object.keys(obj);
}

let arr = [1, 1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 9, 0, 0];
console.log(uniqueArray(arr));

遍历数组,将元素作为键放入对象中。最后通过 Object.keys 取出对象的键即可得到去重后的数组。

这种方法的时间复杂度为 O(n),但结果数组为字符串数组。如果需要转换为数字数组,还需要进行一次类型转换。

双重 for 循环​

filter + indexOf​

forEach + includes​

先 sort 再遍历​

sort + reduce​

Set​

Object 键值对​