请用 JavaScript 实现一个数组去重的方法,要求性能最优。

各位靓仔靓女,欢迎来到今天的“数组去重,快到飞起”专场讲座!我是你们的老朋友,专门解决疑难杂症的码农老王。今天咱们不搞虚的,直接上硬货,用JavaScript把数组去重玩出花来,保证你的代码跑得比博尔特还快!

开场白:为啥要去重?

先别急着写代码,咱们得知道为啥要去重。想象一下,你从数据库里捞了一堆数据,结果里面全是重复的,不仅浪费存储空间,还影响后续的计算。就好比你买了一箱苹果,打开一看,全是坏的,那不得气死?所以,去重就是为了保证数据的纯洁性,提高效率,减少bug。

第一式:Set大法好!

ES6给我们带来了Set这个神器,它最大的特点就是:不允许重复!简直就是为去重量身定做。

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

// 或者更简洁:
const uniqueBySetShort = arr => [...new Set(arr)];

// 示例
const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = uniqueBySet(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

优点: 代码简洁,可读性高,性能不错,尤其是在数据量不大时。

缺点: 不适用于复杂数据类型(比如对象),因为Set判断对象是否重复是基于引用,而不是内容。

第二式:indexOf/includes 配合循环

这是最基础的去重方法,原理很简单:循环遍历数组,如果当前元素不在新数组里,就把它加进去。

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

// 使用 includes
function uniqueByIncludes(arr) {
    const newArray = [];
    for (let i = 0; i < arr.length; i++) {
      if (!newArray.includes(arr[i])) {
        newArray.push(arr[i]);
      }
    }
    return newArray;
  }

// 示例
const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = uniqueByIndexOf(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

优点: 兼容性好,所有浏览器都支持。

缺点: 性能较差,每次循环都要在newArray中查找,时间复杂度是O(n^2)。数据量越大,速度越慢,慢到你想砸电脑!

第三式:对象(或Map)Hash法

这种方法利用对象的键值对特性,键是唯一的,所以可以用来去重。

function uniqueByObject(arr) {
  const obj = {};
  const newArray = [];
  for (let i = 0; i < arr.length; i++) {
    if (!obj[arr[i]]) {
      obj[arr[i]] = true; // 键名可以是任意值,这里用 true
      newArray.push(arr[i]);
    }
  }
  return newArray;
}

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

// 示例
const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = uniqueByObject(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

优点: 性能比indexOf好很多,时间复杂度接近O(n)。

缺点:

  • 无法区分数字和字符串类型的数字(比如1'1'会被认为是同一个键)。
  • 键名会被强制转换为字符串。
  • 无法去重复杂数据类型(对象等)。

第四式:filter 配合 indexOf

这种方法利用filter函数和indexOf方法,代码简洁,但性能一般。

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

// 示例
const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = uniqueByFilter(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

优点: 代码简洁,可读性高。

缺点: 性能较差,因为indexOf在每次迭代中都会遍历数组,时间复杂度是O(n^2)。

第五式:排序后去重

这种方法先对数组进行排序,然后遍历排序后的数组,相邻元素如果相同就跳过。

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

// 示例
const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = uniqueBySort(myArray);
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

优点: 可以保证去重后的数组是有序的。

缺点:

  • 会改变原数组(如果不想改变原数组,需要先复制一份)。
  • 如果数组元素是对象,需要自定义排序规则。
  • 排序本身也是需要时间的,所以性能不一定最好。

第六式:终极大法,结合使用!

没有一种方法是万能的,我们需要根据实际情况选择最合适的方法。比如,如果数据量不大,可以使用Setfilter。如果数据量很大,可以使用对象Hash法。如果需要保证去重后的数组有序,可以使用排序后去重。

性能大比拼(理论分析)

方法 时间复杂度 空间复杂度 适用场景
Set O(n) O(n) 数据量不大,类型简单
indexOf/includes O(n^2) O(n) 数据量非常小,对性能要求不高
对象Hash O(n) O(n) 数据量大,类型简单,不区分数字和字符串
Map Hash O(n) O(n) 数据量大,类型简单,区分数字和字符串
filter + indexOf O(n^2) O(n) 代码简洁,数据量小
排序后去重 O(n log n) O(1) 需要保证去重后的数组有序,需要自定义排序规则时

实战演练:复杂数据类型去重

上面提到的方法,对于简单的数据类型(数字、字符串)效果很好,但是对于复杂的数据类型(对象),就有点力不从心了。因为对象是基于引用比较的,即使两个对象的内容完全一样,它们也是不同的对象。

解决方案:自定义比较函数

我们需要自己定义一个比较函数,判断两个对象是否相等。

function uniqueByObjectContent(arr, compareFunction) {
    const newArray = [];
    const seen = new Map(); // 使用 Map 存储已经比较过的对象的字符串表示

    for (const obj of arr) {
        const objString = JSON.stringify(obj); // 将对象转换为字符串表示
        if (!seen.has(objString)) {
            newArray.push(obj);
            seen.set(objString, true);
        }
    }

    return newArray;
}

// 示例
const myArray = [
  { id: 1, name: '张三' },
  { id: 2, name: '李四' },
  { id: 1, name: '张三' },
  { id: 3, name: '王五' }
];

const uniqueArray = uniqueByObjectContent(myArray);
console.log(uniqueArray);
// 输出:
// [
//   { id: 1, name: '张三' },
//   { id: 2, name: '李四' },
//   { id: 3, name: '王五' }
// ]

// 另一个更灵活的方式:允许自定义比较函数

function uniqueByCustomCompare(arr, compareFunction) {
    const newArray = [];
    for (const item of arr) {
        const isDuplicate = newArray.some(existingItem => compareFunction(item, existingItem));
        if (!isDuplicate) {
            newArray.push(item);
        }
    }
    return newArray;
}

// 示例:使用自定义比较函数
const myArray2 = [
    { id: 1, name: '张三' },
    { id: 2, name: '李四' },
    { id: 1, name: '张三' },
    { id: 3, name: '王五' }
];

function compareObjects(obj1, obj2) {
    return obj1.id === obj2.id && obj1.name === obj2.name;
}

const uniqueArray2 = uniqueByCustomCompare(myArray2, compareObjects);
console.log(uniqueArray2);
// 输出与之前相同

注意:

  • JSON.stringify 的方式适用于对象属性顺序一致的情况。如果对象属性顺序不一致,即使内容相同,也会被认为是不同的对象。
  • 自定义比较函数的方式更加灵活,可以根据实际需求定义比较规则。

高级技巧:利用 Lodash 库

如果你不想自己写代码,可以使用 Lodash 库,它提供了很多方便的函数,包括数组去重。

// 首先,安装 Lodash: npm install lodash
const _ = require('lodash');

const myArray = [1, 2, 2, 3, 4, 4, 5];
const uniqueArray = _.uniq(myArray); // 简单数据类型去重
console.log(uniqueArray); // 输出: [1, 2, 3, 4, 5]

const myArray2 = [
  { id: 1, name: '张三' },
  { id: 2, name: '李四' },
  { id: 1, name: '张三' },
  { id: 3, name: '王五' }
];

const uniqueArray2 = _.uniqBy(myArray2, 'id'); // 根据 id 属性去重
console.log(uniqueArray2);
// 输出:
// [
//   { id: 1, name: '张三' },
//   { id: 2, name: '李四' },
//   { id: 3, name: '王五' }
// ]

总结:

数组去重的方法有很多,选择哪种方法取决于你的具体需求。记住,没有银弹,只有最合适的解决方案。

最后的忠告:

  • 在追求性能的同时,也要注意代码的可读性和可维护性。
  • 不要过度优化,只有在性能成为瓶颈时才需要考虑优化。
  • 多学习,多实践,才能成为真正的编程高手!

好了,今天的讲座就到这里,希望大家有所收获。记住,写代码就像谈恋爱,要用心,要投入,才能写出让人心动的代码!下次再见!

发表回复

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