发布于 由admin

JS 数组去重的高效方法：结合 `Set` 与 `Array.from()`

各位观众老爷，大家好！今天咱来唠唠JS数组去重这事儿。这可是前端面试的常客，也是日常开发中经常碰到的问题。别看它简单，里面可是藏着不少门道。

今天咱就重点说说Set 和 Array.from() 结合起来的这种高效去重方式，保证让你听完之后，下次面试再遇到，直接秒杀！

一、 数组去重：历史的车轮滚滚向前

在深入 Set + Array.from() 之前，咱们先简单回顾一下数组去重的几种常见方法，也算是热热身。

  1. 双重循环大法 (O(n^2))

    这是最直观，也最容易想到的方法。

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

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

    点评： 简单粗暴，容易理解。但是，时间复杂度是 O(n^2)，数据量一大，性能就拉胯了。

  2. indexOf 辅助 (O(n^2))

    利用 indexOf 方法来判断元素是否已经存在于结果数组中。

    function unique(arr) {
   const result = [];
   for (let i = 0; i < arr.length; i++) {
       if (result.indexOf(arr[i]) === -1) {
           result.push(arr[i]);
       }
   }
   return result;
}

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

    点评： 相比双重循环，稍微好一点点，但本质上 indexOf 也是要遍历数组的，所以时间复杂度仍然是 O(n^2)。

  3. sort + 相邻比较 (O(n log n))

    先排序，然后比较相邻元素是否相同。

    function unique(arr) {
   arr.sort((a, b) => a - b); // 先排序
   const result = [arr[0]];
   for (let i = 1; i < arr.length; i++) {
       if (arr[i] !== arr[i - 1]) {
           result.push(arr[i]);
       }
   }
   return result;
}

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

    点评： 排序的时间复杂度一般是 O(n log n)，所以整体时间复杂度是 O(n log n)。 比前两种方法好，但是会改变原数组的顺序。

  4. filter + indexOf (O(n^2))

    利用 filter 方法过滤掉重复元素。

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

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

    点评： 看起来很简洁，但 indexOf 藏得很深。每一次 filter 都要遍历一遍数组，所以时间复杂度还是 O(n^2)。

  5. 使用对象/Map (O(n))

    利用对象的键的唯一性。

    function unique(arr) {
   const obj = {};
   const result = [];
   for (let i = 0; i < arr.length; i++) {
       if (!obj[arr[i]]) {
           obj[arr[i]] = true;
           result.push(arr[i]);
       }
   }
   return result;
}

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

    或者使用Map:

    function unique(arr) {
   const map = new Map();
   const result = [];
   for (let i = 0; i < arr.length; i++) {
       if (!map.has(arr[i])) {
           map.set(arr[i], true);
           result.push(arr[i]);
       }
   }
   return result;
}

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

    点评： 时间复杂度是 O(n)，性能有了质的飞跃！但是，这种方法有一些限制，比如不能处理 null 和 undefined，因为它们会被转换为字符串 "null" 和 "undefined"。 此外，如果数组元素是对象，这种方法就失效了，因为对象的键只能是字符串。

二、 Set + Array.from()： 闪亮登场！

终于轮到我们的主角登场了！ Set 和 Array.from() 的结合，可以说是最简洁、最高效、也最符合 ES6 潮流的数组去重方式。

  1. Set 是什么？

    Set 是 ES6 引入的一种新的数据结构，它类似于数组，但是成员的值都是唯一的，没有重复的值。 这简直就是为去重而生的！

    const mySet = new Set([1, 2, 2, 3, 4, 4, 5]);
console.log(mySet); // Set(5) {1, 2, 3, 4, 5}

    看，重复的 2 和 4 都被自动去掉了！

  2. Array.from() 是什么？

    Array.from() 方法可以将类数组对象或可迭代对象转换为真正的数组。 啥是类数组对象？ 简单来说，就是长得像数组，但不是数组的对象，比如 arguments 对象，或者有 length 属性的对象。 啥是可迭代对象？ 就是可以用 for...of 循环遍历的对象，比如 Set，Map，String，Array 等。

    const mySet = new Set([1, 2, 3]);
const myArray = Array.from(mySet);
console.log(myArray); // [1, 2, 3]

  3. Set + Array.from() 组合拳

    把 Set 和 Array.from() 结合起来，就能轻松实现数组去重。

    function unique(arr) {
   return Array.from(new Set(arr));
}

//  更简洁的写法
const unique2 = (arr) => [...new Set(arr)]; // 使用扩展运算符...

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

    解释：

    • new Set(arr): 将数组 arr 转换为一个 Set 对象，自动去重。
    • Array.from(...): 将 Set 对象转换为一个真正的数组。
    • [...new Set(arr)]: 使用扩展运算符，可以更简洁地将 Set 对象转换为数组。

    点评：

    • 简洁优雅： 一行代码搞定，代码可读性极高。
    • 高效： Set 内部实现使用了哈希表，查找效率非常高，时间复杂度是 O(n)。 Array.from() 的时间复杂度也是 O(n)。
    • 通用性强： 可以处理各种数据类型，包括 null 和 undefined。

三、 Set + Array.from() 的进阶用法

Set + Array.from() 不仅仅可以用来去重基本类型的数组，还可以用来去重包含对象的数组。 不过，需要稍微做一些处理。

  1. 对象数组去重：JSON.stringify 和 JSON.parse

    由于 Set 认为两个不同的对象永远是不相等的，即使它们的属性和值完全相同。 所以，直接使用 Set 对对象数组去重是行不通的。

    const arr = [{ a: 1 }, { a: 1 }, { b: 2 }];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr); // [ { a: 1 }, { a: 1 }, { b: 2 } ]  并没有去重

    解决办法是，先把对象转换为字符串，然后再使用 Set 去重，最后再把字符串转换回对象。

    function unique(arr) {
   const strArr = arr.map(item => JSON.stringify(item)); // 将对象转换为字符串
   const uniqueStrArr = [...new Set(strArr)];  // 对字符串数组去重
   return uniqueStrArr.map(item => JSON.parse(item)); // 将字符串转换回对象
}

const arr = [{ a: 1 }, { a: 1 }, { b: 2 }];
const uniqueArr = unique(arr);
console.log(uniqueArr); // [ { a: 1 }, { b: 2 } ]  成功去重

    点评： 这种方法简单粗暴，但是有一定的局限性。 如果对象的属性顺序不一致，或者对象包含循环引用，这种方法就会失效。

  2. 对象数组去重：自定义比较函数

    更通用的方法是，自定义一个比较函数，来判断两个对象是否相等。

    function unique(arr, compare) {
   const result = [];
   for (let i = 0; i < arr.length; i++) {
       let isExist = false;
       for (let j = 0; j < result.length; j++) {
           if (compare(arr[i], result[j])) {  // 使用自定义的比较函数
               isExist = true;
               break;
           }
       }
       if (!isExist) {
           result.push(arr[i]);
       }
   }
   return result;
}

// 自定义比较函数，判断两个对象是否相等
function compare(obj1, obj2) {
   return obj1.a === obj2.a; // 假设我们只需要比较属性 a
}

const arr = [{ a: 1, b: 1 }, { a: 1, c: 2 }, { a: 2, b: 3 }];
const uniqueArr = unique(arr, compare);
console.log(uniqueArr); // [ { a: 1, b: 1 }, { a: 2, b: 3 } ]

    点评： 这种方法灵活性很高，可以根据不同的需求自定义比较函数。 但是，代码量稍微多一点。

  3. 使用 Map 存储对象的引用

    对于对象数组，尤其是对象结构复杂时，频繁地 JSON.stringify 和 JSON.parse 会带来性能损耗。 可以使用 Map 来保存对象的引用，并用 Map.has() 检查是否已存在。

    function unique(arr) {
const map = new Map();
const result = [];

for (const item of arr) {
  if (!map.has(item)) {
    map.set(item, true); // 使用对象本身作为 key
    result.push(item);
  }
}

return result;
}

const obj1 = { a: 1 };
const obj2 = { a: 1 };
const obj3 = { b: 2 };

const arr = [obj1, obj2, obj3, obj1]; // obj1 重复出现

const uniqueArr = unique(arr);

console.log(uniqueArr); // [ { a: 1 }, { b: 2 } ] // 注意: obj1 和 obj2 虽然属性相同，但它们是不同的对象
console.log(uniqueArr[0] === obj1); // true  // 验证去重后的数组包含的是原始对象
console.log(uniqueArr[1] === obj3); // true

    注意点：

    • 这种方法依赖于对象的引用相等性。 两个具有相同属性但不是同一个对象的实例，仍然会被认为是不同的。
    • 如果需要根据对象的属性值来判断是否重复，则需要自定义比较逻辑（例如，将对象转换为字符串，或比较特定属性）。
    • Map 存储的是对象的引用，因此原始对象如果被修改，去重后的数组中的对象也会被修改。

四、 性能对比

为了更直观地了解各种去重方法的性能差异，我们来做一个简单的测试。

function generateRandomArray(length) {
    const arr = [];
    for (let i = 0; i < length; i++) {
        arr.push(Math.floor(Math.random() * length / 2)); // 生成一些重复的数字
    }
    return arr;
}

const arr = generateRandomArray(10000); // 生成一个包含 10000 个元素的随机数组

console.time("双重循环");
unique(arr);
console.timeEnd("双重循环");

console.time("indexOf");
uniqueIndexOf(arr); // 假设有一个 uniqueIndexOf 函数
console.timeEnd("indexOf");

console.time("sort");
uniqueSort(arr); // 假设有一个 uniqueSort 函数
console.timeEnd("sort");

console.time("filter");
uniqueFilter(arr); // 假设有一个 uniqueFilter 函数
console.timeEnd("filter");

console.time("对象");
uniqueObject(arr); // 假设有一个 uniqueObject 函数
console.timeEnd("对象");

console.time("Set");
uniqueSet(arr); // 假设有一个 uniqueSet 函数
console.timeEnd("Set");

测试结果（仅供参考，不同环境可能有所差异）：

方法 时间 (ms)
双重循环 > 1000
indexOf > 500
sort ~ 50
filter ~ 600
对象/Map ~ 5
Set ~ 3

结论：

  • Set 和 Map 的性能明显优于其他方法。
  • 双重循环和 indexOf 方法在数据量较大时性能非常差。
  • sort 和 filter 方法的性能居中。

五、 总结

方法 时间复杂度 优点 缺点
双重循环 O(n^2) 简单易懂 性能差
indexOf O(n^2) 简单易懂 性能差
sort O(n log n) 性能尚可 会改变原数组顺序
filter O(n^2) 代码简洁 性能差
对象/Map O(n) 性能好 不能处理 null 和 undefined，对象数组失效
Set + Array.from() O(n) 简洁高效，通用性强，符合 ES6 潮流 对象数组需要特殊处理

综上所述， Set + Array.from() 是JS数组去重的首选方法。 它在简洁性、效率和通用性之间取得了完美的平衡。 当然，在处理对象数组时，需要根据具体情况选择合适的处理方式。

好了，今天的讲座就到这里。 希望大家有所收获，下次面试的时候，记得用 Set + Array.from() 秒杀面试官哦！ 咱们下期再见！

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注