# 数组去重

  1. 方法一:双重循环 + 新数组
// 数组去重 version1
// 双重循环 -> 使用一个新数组保存去重后的数组
function unique(array) {
  let res = []; // 去重后数组
  for (var i = 0, arrLen = array.length; i < arrLen; i++) {
    for (var j = 0, resLen = res.length; j < resLen; j++) {
      if (array[i] === res[j]) {
        break;
      }
    }
    if (j === resLen) { // array[i] 是唯一的,循环出来的 j 一定会等于 resLen
      res.push(array[i]);
    }
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  1. 方法二:indexOf + 新数组
// 数组去重 version2
// 使用一个新数组 + indexOf
function unique(array) {
  let res = [];
  for (let i = 0, arrLen = array.length; i < arrLen; i++) {
    const current = array[i];
    if (res.indexOf(current) === -1) { // 当另一个数组中不存在这个元素的时候才放进去
      res.push(current);
    }
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
  1. 方法三:利用 filter 方法
// 去重
// 使用 filter 实现
function unique(array) {
  let res = array.filter((item, index, arr) => {
    return arr.indexOf(item) === index;
  });
  return res;
}
1
2
3
4
5
6
7
8
function sortUnique(array) {
  let res = array.sort().filter((item, index, arr) => {
    return !index || item !== arr[index - 1];
  })
  return res;
}
1
2
3
4
5
6
  1. 方法四:利用 includes 方法实现
// 去重
// includes 实现
function unique(array) {
  let res = [];
  array.forEach(item => {
    if (!res.includes(item)) {
      res.push(item);
    }
  })
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
  1. 方法五:排序后去重
// 去重 version3
// 排序后去重 -> 只需要比较排好序的数组中的前后项是否相等 -> 不相等就加进结果数组
function unique(array) {
  let res = [];
  let sortedArr = array.sort();
  // console.log(sortedArr);
  for (let i = 0, len = sortedArr.length; i < len; i++) {
    if (sortedArr[i] !== sortedArr[i + 1]) { // 前后项判断
      res.push(sortedArr[i]);
    }
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// sort 版本去重优化
function betterUnique(array) {
  let res = [];
  let sortedArr = array.sort();
  for (let i = 0, len = sortedArr.length; i < len; i++) {
    if (sortedArr[i] !== res[res.length - 1]) { // 和已经确定的数组进行判断
      res.push(sortedArr[i]);
    }
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
function uniqueSeen(array) {
  let res = [];
  let sortedArr = array.sort();
  let seen;
  for (let i = 0, len = sortedArr.length; i < len; i++) {
    if (!i || seen !== sortedArr[i]) {
      res.push(sortedArr[i]);
    }
    seen = sortedArr[i];
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
  1. 方法六:利用 reduce 方法
// 去重
// reduce 实现
function unique(array) {
  return array.sort().reduce((res, cur) => {
    if (res.length === 0 || res[res.length - 1] !== cur) { // 结果最后一个和当前项
      res.push(cur);
    }
    return res;
  }, []); // 初始为空
}
1
2
3
4
5
6
7
8
9
10
  1. 方法七:键值对方式实现
// 数组去重
// Object 键值对实现
// 使用一个空的对象,把数组的值存成对象的 key,后续元素判断 key 是否存在
function unique(array) {
  let obj = {};
  return array.filter((item) => { // item + item 避免把 1 和 '1' 判断成同一个值
    return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true);
  });
}
1
2
3
4
5
6
7
8
9
function unique2(array) {
  let obj = {};
  let res = [];
  for (let i = 0, len = array.length; i < len; i++) {
    const item = array[i];
    if (!obj[typeof item + JSON.stringify(item)]) { // 如果该 key 在对象中不存在
      obj[typeof item + JSON.stringify(item)] = 1;
      res.push(item);
    }
  }
  return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
  1. 方法八:利用 map 实现
// 数组去重
// map 实现
function unique(array) {
  let map = new Map();
  return array.filter(item => !map.has(item) && map.set(item, 1));
}
1
2
3
4
5
6
  1. 方法九:双指针实现
// 去重
// 双指针 -> 快慢指针进行数组元素遍历  
// 快指针不停向后走,和慢指针位置的值判断是否相等,遇到不重复元素的时候停止,使用 splice(start, count) 删除中间重复的元素
function unique(array) {
  const size = array.length;
  let slowP = 0;
  for (let fastP = 0; fastP < size; fastP++) {
    if (array[slowP] !== array[fastP]) {
      slowP++;
      array.splice(slowP, fastP - slowP);
      // array[slowP] = array[fastP];
    }
  }
  return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  1. 方法十:使用链表实现
// 去重
// 使用链表
function unique(head) {
  if (head == null || !head.next) return head;
  let cur = head;
  while(cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next;
    } else {
      cur = cur.next;
    }
  }
  return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  1. 方法十一:Set 数据结构实现
// 数组去重
// set 实现
function unique(array) {
  // return Array.from(new Set(array));
  return [...new Set(array)];
}
1
2
3
4
5
6
Last Updated: 5/6/2020, 11:48:16 AM