数组去重-Map实现

DangoSky 发布于2019-08-23 10:48 / 1594人阅读

摘要：问题由来遇到一道面试题找到数组中第一个非重复的数。下面来通过代码解决三个问题数组去重去重前去重后主要思路创建一个空，遍历原始数组，把数组的每一个元素作为存到中，因为中不会出现相同的值，所以最终得到的中的所有值就是去重后的结果。

问题由来

遇到一道面试题：找到数组中第一个非重复的数。

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
第一个非重复的数为 3

最简单的想法就是两层 for 循环遍历数组，这样的时间复杂度是 O(n^2)。而更高效的方式，是使用hash Map，可将时间复杂降为O(n)。

其实这个题目可以衍生出三个类似的问题：

数组去重

找到数组中重复的数

找到数组中第一个非重复的数

我准备用ES6中的 Map数据结构来解决这三个问题，在这之前有必要先梳理下Map的主要知识点。

Map基础梳理

JavaScript 的对象（Object），本质上是键值对的集合（Hash 结构），但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。为了解决这个问题，ES6 提供了 Map 数据结构。它类似于对象，也是键值对的集合，但是“键”的范围不限于字符串，各种类型的值（包括对象）都可以当作键。也就是说，Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。

例如Map构造函数接受一个数组作为其参数：

const map = new Map([
  [1, "张三"],
  [2, "李四"]
]);
// 0:{1 => "张三"}
// 1:{2 => "李四"}

Map实例的属性和操作方法：

size：返回成员总数

set(key, value)：添加新的键值

get(key)：读取键对应的值

has(key)：是否有某个键

delete(key)：删除某个键

clear()：清空

Map实例的遍历方法：

keys()：返回键名的遍历器。

values()：返回键值的遍历器。

entries()：返回键值对的遍历器。

forEach()：遍历 Map 的所有成员。

下面来通过代码解决三个问题：

数组去重

去重前：[ 1, 1, 2, 2, 3, 4, 4, 5 ]
去重后：[ 1, 2, 3, 4, 5 ]

主要思路：创建一个空Map，遍历原始数组，把数组的每一个元素作为key存到Map中，因为Map中不会出现相同的key值，所以最终得到的Map中的所有key值就是去重后的结果。

function arrayNonRepeatfy(arr) {
  let hashMap = new Map();
  let result = new Array();  // 数组用于返回结果
  for (let i = 0; i < arr.length; i++) {
    if(hashMap.has(arr[i])) { // 判断 hashMap 中是否已有该 key 值
      hashMap.set(arr[i], true);  // 后面的true 代表该 key 值在原始数组中重复了，false反之
    } else {  // 如果 hashMap 中没有该 key 值，添加
      hashMap.set(arr[i], false);  
      result.push(arr[i]);
    }
  } 
  return result;
}

let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(arrayNonRepeatfy(arr)); // [ 1, 2, 3, 4, 5, "a", "b" ]

上面最终产生的Map不仅可以达到去重的效果，而且对每一元素的重复性都做了标注，这样想找到找到数组中重复的数就很方便了：

console.log(hashMap);
/*
0:{1 => true} {key: 1, value: true}
1:{2 => false} {key: 2, value: false}
2:{3 => true} {key: 3, value: true}
3:{4 => false} {key: 4, value: false}
4:{5 => true} {key: 5, value: true}
5:{"a" => true} {key: "a", value: true}
6:{"b" => false} {key: "b", value: false}
*/

找到数组中重复的数

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
[ 1, 2, 4 ]
接上一节末尾，既然hashMap中记录了每一个元素的重复情况，找到重复的数就很简单了，遍历最终得到的hashMap，值为 true 对应的键就是重复的数：

function findRepeatNumInArray(arr) {
  let hashMap = new Map();
  let result = new Array();
  for (let i = 0; i < arr.length; i++) {
    hashMap.set(arr[i], hashMap.has(arr[i]))
  }
  // 得到 hashMap 后，对其进行遍历，值为 true，对应的键就是重复的数
  for(let [key, value] of hashMap.entries()) { 
    if(value === true) {
      result.push(key);
    }
  }
  return result; 
}

let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(findRepeatNumInArray(arr));

找到数组中第一个非重复的数

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
3
代码与上一节的差不多，遍历最终得到的hashMap，第一个值为 false 对应的键就是第一个非重复数字:

function findFirstNonRepeat(arr) {
  let hashMap = new Map();
  for (let i = 0; i < arr.length; i++) {
    hashMap.set(arr[i], hashMap.has(arr[i]))
  }
  // 找到第一个值为 false 的，就代表第一个非重复数，return 就好了
  for(let [key, value] of hashMap.entries()) {
    if(value === false) {
      return key;
    }
  }
  return "全部重复";
}

let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(findFirstNonRepeat(arr));

总结，三类问题的核心其实就是：利用 Map 存储每一个数字的重复情况。

云服务器 GPU云服务器数组去重数组去重二维数组去重 php数组去重

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96693.html

JavaScript数组方法之数组去重方法

摘要：工作过程中经常会用到数组去重，用到的时候往往一时想不到好方法，所以这里来总结一下去重方法。和方法分别为添加成员方法和得到键值方法。因此，利用方法也可以实现数组的去重。工作过程中经常会用到数组去重，用到的时候往往一时想不到好方法，所以这里来总结一下去重方法。使用es6去重代码很简单，而且ES6已经相当普及了。所以先来介绍一下es6中的方法。 1.ES6中Map结构方法 function...

CarlBenjamin 2019-08-22 15:18 评论0 收藏0
JavaScript 实现数组更多的高阶函数

摘要：实现数组更多的高阶函数吾辈的博客原文场景虽说人人平等，但有些人更加平等。若是有一篇适合萌新阅读的自己实现数组更多操作的文章，情况或许会发生一些变化。类似于的初始值，但它是一个函数，避免初始值在所有分组中进行累加。 JavaScript 实现数组更多的高阶函数吾辈的博客原文: https://blog.rxliuli.com/p/fc... 场景虽说人人平等，但有些人更加平等。为...

aervon 2019-08-23 18:31 评论0 收藏0
好像不是最全的数组去重方法

摘要：最简单粗暴地方式，两重循环两个因为两个因为排序，如果相同就会挨着先放数组第一个元素无法判断对象对象数组去重方法补充我想说一下与相同点他们都是用来遍历数组的。不同点能有返回值，没有返回值。这一篇文章，我们讲解一下数组去重。 1.最简单粗暴地方式，两重for循环 let arr = [9, 5, 6, 5, 1, 1, true, 5, true]; for (var i = 0; i ...

AnthonyHan 2019-08-23 14:30 评论0 收藏0
JavaScript数组去重—ES6的两种方式

摘要：数组的方法方法创建一个新的数组，新数组中的元素是通过检查指定数组中符合条件的所有元素。可选，执行函数时的值。删除所有的键值对，没有返回值。返回一个布尔值，表示某个键是否在当前对象之中。说明 JavaScript数组去重这个问题，经常出现在面试题中，以前也写过一篇数组去重的文章，（JavaScript 数组去重的多种方法原理详解）但感觉代码还是有点不够简单，今天和大家再说两种方法，代码...

FrancisSoung 2019-08-21 17:26 评论0 收藏0
JavaScript数组去重—ES6的两种方式

摘要：数组的方法方法创建一个新的数组，新数组中的元素是通过检查指定数组中符合条件的所有元素。可选，执行函数时的值。删除所有的键值对，没有返回值。返回一个布尔值，表示某个键是否在当前对象之中。说明 JavaScript数组去重这个问题，经常出现在面试题中，以前也写过一篇数组去重的文章，（JavaScript 数组去重的多种方法原理详解）但感觉代码还是有点不够简单，今天和大家再说两种方法，代码...

lijinke666 2019-08-01 17:57 评论0 收藏0