二、JavaScript专题之数组去重

发表于 分类于 阅读次数：

在面试中，我们常常会遇到数组去重的问题，这里整理一下。

双重循环去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function uniq(array) {
  let res = [];
  for (var i = 0; i < array.length; i++) {
    for (var j = 0, len = res.length; j < len; j++) {
      if (array[i] === res[j]) {
        break;
      }
    }
    if (j === len) res.push(array[i]);
  }
  return res;
}

// 测试
var arr = [1, 2, 1, "3", "2", "1"];
console.log(uniq(arr)); //[1, 2, "3", "2", "1"]

双循环去重优化

思路：获取没重复的最右一值放入新数组(判断值得右侧有无重复)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * 推荐的方法
 * 效率较高
 * 实现思路：获取没重复的最右一值放入新数组。
 * （检测到有重复值时终止当前循环同时进入顶层循环的下一轮判断）*/
function uniq(array) {
  var res = [],
    len = array.length;
  for (var i = 0; i < len; i++) {
    for (var j = i + 1; j < len; j++) {
      if (array[i] === array[j]) {
        i++;
        j = i;
      }
    }
    res.push(array[i]);
  }
  return res;
}

IndexOf

利用 IndexOf 简化内层循环：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * 新建一新数组，遍历传入数组，值不在新数组就push进该新数组中
 * IE8以下不支持数组的indexOf方法
 * */
function uniq(array) {
  let res = [];
  for (var i = 0; i < array.length; i++) {
    if (res.indexOf(array[i]) === -1) {
      res.push(array[i]);
    }
  }
  return res;
}

排序后相邻去除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 * 给传入数组排序，排序后相同值相邻，
 * 然后遍历时,新数组只加入不与前一值重复的值。
 * 会打乱原来数组的顺序
 * [2, "2", 2, "2"]排序会有问题
 * */
function uniq(array) {
  array.sort();
  let res = [array[0]];
  for (var i = 1; i < array.length; i++) {
    if (array[i] !== array[i - 1]) {
      res.push(array[i]);
    }
  }
  return res;
}

对象键值去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * 速度最快， 占空间最多（空间换时间）
 *
 * 该方法执行的速度比其他任何方法都快， 就是占用的内存大一些。
 * 现思路：新建一js对象以及新数组，遍历传入数组时，判断值是否为js对象的键，
 * 不是的话给对象新增该键并放入新数组。
 * 注意点：判断是否为js对象键时，会自动对传入的键执行“toString()”，
 * 不同的键可能会被误认为一样，例如n[val]-- n[1]、n["1"]；
 * 解决上述问题还是得调用“indexOf”。*/
function uniq(array) {
  var res = [],
    temp = {};
  array.forEach((val) => {
    let type = typeof val;
    if (!temp[val]) {
      temp[val] = [type];
      res.push(val);
    } else if (temp[val].indexOf(type) < 0) {
      temp[val].push(type);
      res.push(val);
    }
  });
  return res;
}

数组下标法

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * 实现思路：如果当前数组的第i项在当前数组中第一次出现的位置不是i，
 * 那么表示第i项是重复的，忽略掉。否则存入结果数组。
 * */
function uniq(array) {
  var res = [];
  array.forEach((v, i) => {
    if (array.indexOf(v) === i) {
      res.push(v);
    }
  });
  return res;
}

filter

ES5 提供了 filter 方法，我们可以用来简化外层循环

1
2
3
4
5
6
function unique(array) {
  var res = array.filter(function (item, index, array) {
    return array.indexOf(item) === index;
  });
  return res;
}

利用 ES6 的 set

1
2
3
4
5
6
7
8
// 利用Array.from将Set结构转换成数组
function uniq(arr) {
  return Array.from(new Set(arr));
}
// 或者
function unique(array) {
  return [...new Set(array)];
}

写在最后

去重的方式有很多，我们需要知道在合适的场景要选择合适的方法，这样才能达到最优。