Sobird

JavaScript数组去重问题，不论是在面试题，还是真实项目中，都是一个非常常见的问题，本文再次整理以飨读者，同时也是一种自我学习。

双重循环

首选遍历要去重的数组，内层遍历新数组是否存在重复值，如果不存在将新值放入新数组。

function unique(arr) {
  var res = [];
  for(var i = 0; i < arr.length; i++) {
    for(var  j = 0; j < res.length; j++) {
      if(arr[i] === res[j]) {
        break;
      }
    }
    if(j === res.length) {
      res.push(arr[i]);
    }
  }
  return res;
}

对象键值对

利用对象的key不重复的特性来进行去重。早期的YUI框架中的数组去重就是利用了这种特性实现的。下面是YUI中的源码：

var toObject = function(a) { 
  var o = {}; 
  for (var i = 0; i < a.length; i = i+1) {// 这里我调整了下, YUI源码中是i<a.length 
    o[a[i]] = true; 
  } 
  return o; 
}; 
var keys = function(o) { 
  var a=[], i; 
  for (i in o) { 
    if (o.hasOwnProperty(i)) {// 这里, YUI源码中是lang.hasOwnProperty(o, i) 
      a.push(i); 
    } 
  } 
  return a; 
}; 
var yui_uniq= function(a) { return keys(toObject(a)); };

该方法具体实现如下：

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

需要注意的是：

• 无法区分隐式类型转换成字符串后一样的值，比如 1 和 ‘1’
• 无法处理复杂数据类型，比如对象（因为对象作为 key 会变成 [object Object]）
• 特殊数据，比如 ‘__proto__’，因为对象的 __proto__ 属性无法被重写

最终改写实现如下：

function unique(arr) {
  var res = [];
  var obj = {};
  for(var i = 0; i < arr.length; i++) {
    var key = typeof arr[i] + JSON.stringify(arr[i])
    if(!obj[key]) {
      res.push(arr[i]);
      obj[key] = true;
    }
  }
  return res;
}

indexOf方法去重

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

相邻元素去重

这种方法首先调用了数组的排序方法sort()，然后根据排序后的结果进行遍历及相邻元素比对，如果相等则跳过该元素，直到遍历结束。话说jQuery中的数组去重就是这么实现的

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

Map

ES6 提供了 Map 数据结构，我们可以借助该数据结构实现数组去重功能。

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

Set

同时ES6提供了 Set 数据结构，它类似于数组，但是成员的值都是唯一的，没有重复的值。可以更加方便实现数组去重功能。

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

性能测试

点击访问 https://sobird.github.io/blog/JavaScript-Array-Unique-Test.html 可以查看以上方法的性能测试