數(shù)組去重-Map實現(xiàn)

DangoSky 發(fā)布于2019-08-23 10:48 / 1577人閱讀

摘要：問題由來遇到一道面試題找到數(shù)組中第一個非重復的數(shù)。下面來通過代碼解決三個問題數(shù)組去重去重前去重后主要思路創(chuàng)建一個空，遍歷原始數(shù)組，把數(shù)組的每一個元素作為存到中，因為中不會出現(xiàn)相同的值，所以最終得到的中的所有值就是去重后的結果。

問題由來

遇到一道面試題：找到數(shù)組中第一個非重復的數(shù)。

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
第一個非重復的數(shù)為 3

最簡單的想法就是兩層 for 循環(huán)遍歷數(shù)組，這樣的時間復雜度是 O(n^2)。而更高效的方式，是使用hash Map，可將時間復雜降為O(n)。

其實這個題目可以衍生出三個類似的問題：

數(shù)組去重

找到數(shù)組中重復的數(shù)

找到數(shù)組中第一個非重復的數(shù)

我準備用ES6中的 Map數(shù)據(jù)結構來解決這三個問題，在這之前有必要先梳理下Map的主要知識點。

Map基礎梳理

JavaScript 的對象（Object），本質上是鍵值對的集合（Hash 結構），但是傳統(tǒng)上只能用字符串當作鍵。這給它的使用帶來了很大的限制。為了解決這個問題，ES6 提供了 Map 數(shù)據(jù)結構。它類似于對象，也是鍵值對的集合，但是“鍵”的范圍不限于字符串，各種類型的值（包括對象）都可以當作鍵。也就是說，Object 結構提供了“字符串—值”的對應，Map 結構提供了“值—值”的對應，是一種更完善的 Hash 結構實現(xiàn)。

例如Map構造函數(shù)接受一個數(shù)組作為其參數(shù)：

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

Map實例的屬性和操作方法：

size：返回成員總數(shù)

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

get(key)：讀取鍵對應的值

has(key)：是否有某個鍵

delete(key)：刪除某個鍵

clear()：清空

Map實例的遍歷方法：

keys()：返回鍵名的遍歷器。

values()：返回鍵值的遍歷器。

entries()：返回鍵值對的遍歷器。

forEach()：遍歷 Map 的所有成員。

下面來通過代碼解決三個問題：

數(shù)組去重

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

主要思路：創(chuàng)建一個空Map，遍歷原始數(shù)組，把數(shù)組的每一個元素作為key存到Map中，因為Map中不會出現(xiàn)相同的key值，所以最終得到的Map中的所有key值就是去重后的結果。

function arrayNonRepeatfy(arr) {
  let hashMap = new Map();
  let result = new Array();  // 數(shù)組用于返回結果
  for (let i = 0; i < arr.length; i++) {
    if(hashMap.has(arr[i])) { // 判斷 hashMap 中是否已有該 key 值
      hashMap.set(arr[i], true);  // 后面的true 代表該 key 值在原始數(shù)組中重復了，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不僅可以達到去重的效果，而且對每一元素的重復性都做了標注，這樣想找到找到數(shù)組中重復的數(shù)就很方便了：

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}
*/

找到數(shù)組中重復的數(shù)

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
[ 1, 2, 4 ]
接上一節(jié)末尾，既然hashMap中記錄了每一個元素的重復情況，找到重復的數(shù)就很簡單了，遍歷最終得到的hashMap，值為 true 對應的鍵就是重復的數(shù)：

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，對應的鍵就是重復的數(shù)
  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));

找到數(shù)組中第一個非重復的數(shù)

[ 1, 1, 2, 2, 3, 4, 4, 5 ]
3
代碼與上一節(jié)的差不多，遍歷最終得到的hashMap，第一個值為 false 對應的鍵就是第一個非重復數(shù)字:

function findFirstNonRepeat(arr) {
  let hashMap = new Map();
  for (let i = 0; i < arr.length; i++) {
    hashMap.set(arr[i], hashMap.has(arr[i]))
  }
  // 找到第一個值為 false 的，就代表第一個非重復數(shù)，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 存儲每一個數(shù)字的重復情況。

GPU云服務器云服務器數(shù)組去重數(shù)組去重二維數(shù)組去重 php數(shù)組去重

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96693.html

JavaScript數(shù)組方法之數(shù)組去重方法

摘要：工作過程中經常會用到數(shù)組去重，用到的時候往往一時想不到好方法，所以這里來總結一下去重方法。和方法分別為添加成員方法和得到鍵值方法。因此，利用方法也可以實現(xiàn)數(shù)組的去重。工作過程中經常會用到數(shù)組去重，用到的時候往往一時想不到好方法，所以這里來總結一下去重方法。使用es6去重代碼很簡單，而且ES6已經相當普及了。所以先來介紹一下es6中的方法。 1.ES6中Map結構方法 function...

CarlBenjamin 2019-08-22 15:18 評論0 收藏0
JavaScript 實現(xiàn)數(shù)組更多的高階函數(shù)

摘要：實現(xiàn)數(shù)組更多的高階函數(shù)吾輩的博客原文場景雖說人人平等，但有些人更加平等。若是有一篇適合萌新閱讀的自己實現(xiàn)數(shù)組更多操作的文章，情況或許會發(fā)生一些變化。類似于的初始值，但它是一個函數(shù)，避免初始值在所有分組中進行累加。 JavaScript 實現(xiàn)數(shù)組更多的高階函數(shù) 吾輩的博客原文: https://blog.rxliuli.com/p/fc... 場景雖說人人平等，但有些人更加平等。為...

aervon 2019-08-23 18:31 評論0 收藏0
好像不是最全的數(shù)組去重方法

摘要：最簡單粗暴地方式，兩重循環(huán)兩個因為兩個因為排序，如果相同就會挨著先放數(shù)組第一個元素無法判斷對象對象數(shù)組去重方法補充我想說一下與相同點他們都是用來遍歷數(shù)組的。不同點能有返回值，沒有返回值。這一篇文章，我們講解一下數(shù)組去重。 1.最簡單粗暴地方式，兩重for循環(huán) 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數(shù)組去重—ES6的兩種方式

摘要：數(shù)組的方法方法創(chuàng)建一個新的數(shù)組，新數(shù)組中的元素是通過檢查指定數(shù)組中符合條件的所有元素。可選，執(zhí)行函數(shù)時的值。刪除所有的鍵值對，沒有返回值。返回一個布爾值，表示某個鍵是否在當前對象之中。說明 JavaScript數(shù)組去重這個問題，經常出現(xiàn)在面試題中，以前也寫過一篇數(shù)組去重的文章，（JavaScript 數(shù)組去重的多種方法原理詳解）但感覺代碼還是有點不夠簡單，今天和大家再說兩種方法，代碼...

FrancisSoung 2019-08-21 17:26 評論0 收藏0
JavaScript數(shù)組去重—ES6的兩種方式

摘要：數(shù)組的方法方法創(chuàng)建一個新的數(shù)組，新數(shù)組中的元素是通過檢查指定數(shù)組中符合條件的所有元素。可選，執(zhí)行函數(shù)時的值。刪除所有的鍵值對，沒有返回值。返回一個布爾值，表示某個鍵是否在當前對象之中。說明 JavaScript數(shù)組去重這個問題，經常出現(xiàn)在面試題中，以前也寫過一篇數(shù)組去重的文章，（JavaScript 數(shù)組去重的多種方法原理詳解）但感覺代碼還是有點不夠簡單，今天和大家再說兩種方法，代碼...

lijinke666 2019-08-01 17:57 評論0 收藏0