如何高效删除 JavaScript 数组中的重复元素？

前端达人

发布于 2024-07-20 10:39:42

640

发布于 2024-07-20 10:39:42

文章被收录于专栏：前端达人

在日常编程中，我们经常会遇到数组去重的问题。今天，我们就来聊聊如何用JavaScript来优雅地解决这个问题。

问题描述

给定一个包含重复元素的数组，我们希望创建一个新的数组，其中只包含原始数组中的唯一值。例如，如果我们有一个数组 [1, 2, 3, 2, 4, 1, 5]，期望的输出应该是 [1, 2, 3, 4, 5]。

方法一：最原始的方法

我们可以使用最简单的方法——嵌套循环来解决这个问题。遍历每一个元素，检查它是否已经存在于新数组中，如果不存在则添加进去。

function removeDuplicates(arr) {
  const 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;
}
const myArray = [1, 2, 3, 2, 4, 1, 5];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

这个方法虽然直观，但当数组很大时，效率会变得非常低，因为时间复杂度是 O(n²)。

方法二：使用indexOf和filter方法

我们还可以使用 indexOf 方法配合 filter 方法来去重，这样看起来会简洁不少。

function removeDuplicates(arr) {
  return arr.filter((item, pos) => arr.indexOf(item) === pos);
}
const myArray = [1, 2, 3, 2, 4, 1, 5];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

在这个方法中，我们使用 filter 方法创建了一个新数组，只有满足条件的元素才会被包含进来。条件是当前元素的索引应该等于该元素在数组中第一次出现的位置。这种方法代码看起来更简洁，但是它的时间复杂度依然是 O(n²)，因为 indexOf 需要遍历整个数组来查找元素的位置。

使用对象特性优化

在处理大数组去重时，我们可以利用对象的特性来提升性能。通过在对象中记录数组元素，可以有效减少重复元素的检查次数。

function removeDuplicates(arr) {
  const seen = {};
  return arr.filter((item) => {
    if (seen[item]) {
      return false;
    } else {
      seen[item] = true;
      return true;
    }
  });
}
const myArray = [1, 2, 3, 2, 4, 1, 5];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

这个方法创建了一个空对象 seen，然后通过 filter 方法遍历数组。每个元素都会检查是否已存在于 seen 对象中。如果存在，则跳过；否则，加入 seen 对象并保留在新数组中。这种方法对于大数组更高效，但存在一些缺点：

类型转换：对象键只能是字符串或符号，这导致数字和字符串形式的数字无法区分。例如，removeDuplicates([1, "1"]) 会返回 [1]。
对象相等性：所有对象在这个解决方案中被认为是相等的。例如，removeDuplicates([{foo: 1}, {foo: 2}]) 会返回 [{foo: 1}]。

如果你的数组只包含基本类型，并且不需要区分类型，这可以放心使用这个方法。

结合对象和数组的线性搜索

我们可以结合对象和数组的线性搜索方法来解决上述问题。

function removeDuplicates(arr) {
  const prims = { boolean: {}, number: {}, string: {} };
  const objs = [];
  return arr.filter((item) => {
    const type = typeof item;
    if (type in prims) {
      if (prims[type].hasOwnProperty(item)) {
        return false;
      } else {
        prims[type][item] = true;
        return true;
      }
    } else {
      if (objs.indexOf(item) >= 0) {
        return false;
      } else {
        objs.push(item);
        return true;
      }
    }
  });
}
const myArray = [1, 2, 3, 2, 4, 1, 5, { foo: 1 }, { foo: 2 }];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5, { foo: 1 }, { foo: 2 }]

主要优点

分类存储：通过将基本类型和对象类型分别存储，减少了不同类型之间的冲突，逻辑清晰。
高效处理基本类型：使用对象存储基本类型，查找和存储操作的时间复杂度为 O(1)，效率较高。

存在的问题

1、对象类型处理问题：
- 引用比较：代码使用 indexOf 方法判断对象是否存在于数组中，这实际上是比较对象的引用而不是内容。即使两个对象内容相同，但引用不同，indexOf 也会返回 -1，导致内容相同但引用不同的对象被认为是不同的。例如，{ foo: 1 } 和另一个 { foo: 1 } 会被当作两个不同的对象。
- 性能问题：对于大量对象类型的元素，由于 indexOf 方法需要遍历整个数组，时间复杂度为 O(n)，性能较差。
2、不能深度比较：对于嵌套对象或数组，该方法无法进行深度比较。例如，{ foo: [1, 2] } 和 { foo: [1, 2] } 这样的对象，内容相同但引用不同，会被认为是不同的对象。

最终方案：编写深度比较函数

编写深度比较函数 isDeepDataStructureEquality，用来比较两个对象的内容是否相同。

function isDeepDataStructureEquality(a, b) {
    let isEqual = Object.is(a, b);

    if (!isEqual) {
      if (Array.isArray(a) && Array.isArray(b)) {

        isEqual = (a.length === b.length) && a.every(
          (item, idx) => isDeepDataStructureEquality(item, b[idx])
        );
      } else if (
        a && b
        && (typeof a === 'object')
        && (typeof b === 'object')
      ) {
        const aKeys = Object.keys(a);
        const bKeys = Object.keys(b);

        isEqual = (aKeys.length === bKeys.length) && aKeys.every(
          (key, idx) => isDeepDataStructureEquality(a[key], b[key])
        );
      }
    }
    return isEqual;
  }

function removeDuplicates(arr) {
  const primitives = { boolean: {}, number: {}, string: {} };
  const objs = [];
  return arr.filter(item => {
    const type = typeof item;
    if (type in primitives) {
      if (primitives[type].hasOwnProperty(item)) {
        return false;
      } else {
        primitives[type][item] = true;
        return true;
      }
    } else {
      if (objs.some(obj => isDeepDataStructureEquality(obj, item))) {
        return false;
      } else {
        objs.push(item);
        return true;
      }
    }
  });
}

方法三：排序去重

另一种去重方法是先排序数组，然后去除连续重复的元素。

function removeDuplicates(arr) {
  return arr.sort().filter((item, pos, ary) => !pos || item !== ary[pos - 1]);
}
const myArray = [1, 2, 3, 2, 4, 1, 5];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

这个方法首先使用 sort 方法对数组进行排序，然后使用 filter 方法去除连续的重复元素。虽然对已排序的数组很有效，但无法处理对象数组。

方法四：使用 Set 处理对象

对于包含对象的数组，我们可以利用 Set 数据结构来高效去重。因为 Set 只存储唯一值，我们可以将数组转换为 Set，然后再转换回数组。

function removeDuplicates(arr) {
  return [...new Set(arr)];
}
const myArray = [1, 2, 3, 2, 4, 1, 5, { foo: 1 }, { foo: 2 }];
const uniqueArray = removeDuplicates(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5, { foo: 1 }, { foo: 2 }]

这个方法通过 new Set(arr) 创建一个新的集合，然后使用扩展运算符 ... 将集合展开为数组，去重过程简单且高效。

优点
- 简洁：代码非常简洁，只需一行代码即可实现数组去重。
- 高效：Set 数据结构在插入元素时自动去重，性能较好，时间复杂度为 O(n)。
存在的问题
- 对象引用问题：Set 判断元素是否相等时，使用的是同一对象引用。例如，两个内容相同但引用不同的对象 { foo: 1 } 和 { foo: 1 } 会被视为不同的元素。