資訊專(zhuān)欄INFORMATION COLUMN
摘要：?jiǎn)栴}由來(lái)遇到一道面試題找到數(shù)組中第一個(gè)非重復(fù)的數(shù)。下面來(lái)通過(guò)代碼解決三個(gè)問(wèn)題數(shù)組去重去重前去重后主要思路創(chuàng)建一個(gè)空，遍歷原始數(shù)組，把數(shù)組的每一個(gè)元素作為存到中，因?yàn)橹胁粫?huì)出現(xiàn)相同的值，所以最終得到的中的所有值就是去重后的結(jié)果。
問(wèn)題由來(lái)
遇到一道面試題：找到數(shù)組中第一個(gè)非重復(fù)的數(shù)。
[ 1, 1, 2, 2, 3, 4, 4, 5 ]
第一個(gè)非重復(fù)的數(shù)為 3
最簡(jiǎn)單的想法就是兩層 for 循環(huán)遍歷數(shù)組，這樣的時(shí)間復(fù)雜度是 O(n^2)。而更高效的方式，是使用hash Map，可將時(shí)間復(fù)雜降為O(n)。
其實(shí)這個(gè)題目可以衍生出三個(gè)類(lèi)似的問(wèn)題：
數(shù)組去重
找到數(shù)組中重復(fù)的數(shù)
找到數(shù)組中第一個(gè)非重復(fù)的數(shù)
我準(zhǔn)備用ES6中的 Map數(shù)據(jù)結(jié)構(gòu)來(lái)解決這三個(gè)問(wèn)題，在這之前有必要先梳理下Map的主要知識(shí)點(diǎn)。
Map基礎(chǔ)梳理JavaScript 的對(duì)象（Object），本質(zhì)上是鍵值對(duì)的集合（Hash 結(jié)構(gòu)），但是傳統(tǒng)上只能用字符串當(dāng)作鍵。這給它的使用帶來(lái)了很大的限制。為了解決這個(gè)問(wèn)題，ES6 提供了 Map 數(shù)據(jù)結(jié)構(gòu)。它類(lèi)似于對(duì)象，也是鍵值對(duì)的集合，但是“鍵”的范圍不限于字符串，各種類(lèi)型的值（包括對(duì)象）都可以當(dāng)作鍵。也就是說(shuō)，Object 結(jié)構(gòu)提供了“字符串—值”的對(duì)應(yīng)，Map 結(jié)構(gòu)提供了“值—值”的對(duì)應(yīng)，是一種更完善的 Hash 結(jié)構(gòu)實(shí)現(xiàn)。
例如Map構(gòu)造函數(shù)接受一個(gè)數(shù)組作為其參數(shù)：
const map = new Map([
[1, "張三"],
[2, "李四"]
]);
// 0:{1 => "張三"}
// 1:{2 => "李四"}
Map實(shí)例的屬性和操作方法：
size：返回成員總數(shù)
set(key, value)：添加新的鍵值
get(key)：讀取鍵對(duì)應(yīng)的值
has(key)：是否有某個(gè)鍵
delete(key)：刪除某個(gè)鍵
clear()：清空
Map實(shí)例的遍歷方法：
keys()：返回鍵名的遍歷器。
values()：返回鍵值的遍歷器。
entries()：返回鍵值對(duì)的遍歷器。
forEach()：遍歷 Map 的所有成員。
下面來(lái)通過(guò)代碼解決三個(gè)問(wèn)題：
數(shù)組去重去重前：[ 1, 1, 2, 2, 3, 4, 4, 5 ]
去重后：[ 1, 2, 3, 4, 5 ]
主要思路：創(chuàng)建一個(gè)空Map，遍歷原始數(shù)組，把數(shù)組的每一個(gè)元素作為key存到Map中，因?yàn)?b>Map中不會(huì)出現(xiàn)相同的key值，所以最終得到的Map中的所有key值就是去重后的結(jié)果。
function arrayNonRepeatfy(arr) {
let hashMap = new Map();
let result = new Array(); // 數(shù)組用于返回結(jié)果
for (let i = 0; i < arr.length; i++) {
if(hashMap.has(arr[i])) { // 判斷 hashMap 中是否已有該 key 值
hashMap.set(arr[i], true); // 后面的true 代表該 key 值在原始數(shù)組中重復(fù)了，false反之
} else { // 如果 hashMap 中沒(méi)有該 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" ]
上面最終產(chǎn)生的Map不僅可以達(dá)到去重的效果，而且對(duì)每一元素的重復(fù)性都做了標(biāo)注，這樣想找到找到數(shù)組中重復(fù)的數(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ù)組中重復(fù)的數(shù)
[ 1, 1, 2, 2, 3, 4, 4, 5 ]
[ 1, 2, 4 ]
接上一節(jié)末尾，既然hashMap中記錄了每一個(gè)元素的重復(fù)情況，找到重復(fù)的數(shù)就很簡(jiǎn)單了，遍歷最終得到的hashMap，值為 true 對(duì)應(yīng)的鍵就是重復(fù)的數(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 后，對(duì)其進(jìn)行遍歷，值為 true，對(duì)應(yīng)的鍵就是重復(fù)的數(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ù)組中第一個(gè)非重復(fù)的數(shù)
[ 1, 1, 2, 2, 3, 4, 4, 5 ]
3
代碼與上一節(jié)的差不多，遍歷最終得到的hashMap，第一個(gè)值為 false 對(duì)應(yīng)的鍵就是第一個(gè)非重復(fù)數(shù)字:
function findFirstNonRepeat(arr) {
let hashMap = new Map();
for (let i = 0; i < arr.length; i++) {
hashMap.set(arr[i], hashMap.has(arr[i]))
}
// 找到第一個(gè)值為 false 的，就代表第一個(gè)非重復(fù)數(shù)，return 就好了
for(let [key, value] of hashMap.entries()) {
if(value === false) {
return key;
}
}
return "全部重復(fù)";
}
let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(findFirstNonRepeat(arr));
總結(jié)，三類(lèi)問(wèn)題的核心其實(shí)就是：利用 Map 存儲(chǔ)每一個(gè)數(shù)字的重復(fù)情況。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/96693.html
摘要：工作過(guò)程中經(jīng)常會(huì)用到數(shù)組去重，用到的時(shí)候往往一時(shí)想不到好方法，所以這里來(lái)總結(jié)一下去重方法。和方法分別為添加成員方法和得到鍵值方法。因此，利用方法也可以實(shí)現(xiàn)數(shù)組的去重。 工作過(guò)程中經(jīng)常會(huì)用到數(shù)組去重，用到的時(shí)候往往一時(shí)想不到好方法，所以這里來(lái)總結(jié)一下去重方法。使用es6去重代碼很簡(jiǎn)單，而且ES6已經(jīng)相當(dāng)普及了。所以先來(lái)介紹一下es6中的方法。 1.ES6中Map結(jié)構(gòu)方法 function...
摘要：實(shí)現(xiàn)數(shù)組更多的高階函數(shù)吾輩的博客原文場(chǎng)景雖說(shuō)人人平等，但有些人更加平等。若是有一篇適合萌新閱讀的自己實(shí)現(xiàn)數(shù)組更多操作的文章，情況或許會(huì)發(fā)生一些變化。類(lèi)似于的初始值，但它是一個(gè)函數(shù)，避免初始值在所有分組中進(jìn)行累加。 JavaScript 實(shí)現(xiàn)數(shù)組更多的高階函數(shù) 吾輩的博客原文: https://blog.rxliuli.com/p/fc... 場(chǎng)景 雖說(shuō)人人平等，但有些人更加平等。 為...
摘要：最簡(jiǎn)單粗暴地方式，兩重循環(huán)兩個(gè)因?yàn)閮蓚€(gè)因?yàn)榕判?，如果相同就?huì)挨著先放數(shù)組第一個(gè)元素?zé)o法判斷對(duì)象對(duì)象數(shù)組去重方法補(bǔ)充我想說(shuō)一下與相同點(diǎn)他們都是用來(lái)遍歷數(shù)組的。不同點(diǎn)能有返回值，沒(méi)有返回值。 這一篇文章，我們講解一下數(shù)組去重。 1.最簡(jiǎn)單粗暴地方式，兩重for循環(huán) let arr = [9, 5, 6, 5, 1, 1, true, 5, true]; for (var i = 0; i ...
摘要：數(shù)組的方法方法創(chuàng)建一個(gè)新的數(shù)組，新數(shù)組中的元素是通過(guò)檢查指定數(shù)組中符合條件的所有元素。可選，執(zhí)行函數(shù)時(shí)的值。刪除所有的鍵值對(duì)，沒(méi)有返回值。返回一個(gè)布爾值，表示某個(gè)鍵是否在當(dāng)前對(duì)象之中。 說(shuō)明 JavaScript數(shù)組去重這個(gè)問(wèn)題，經(jīng)常出現(xiàn)在面試題中，以前也寫(xiě)過(guò)一篇數(shù)組去重的文章，（JavaScript 數(shù)組去重的多種方法原理詳解）但感覺(jué)代碼還是有點(diǎn)不夠簡(jiǎn)單，今天和大家再說(shuō)兩種方法，代碼...
摘要：數(shù)組的方法方法創(chuàng)建一個(gè)新的數(shù)組，新數(shù)組中的元素是通過(guò)檢查指定數(shù)組中符合條件的所有元素?？蛇x，執(zhí)行函數(shù)時(shí)的值。刪除所有的鍵值對(duì)，沒(méi)有返回值。返回一個(gè)布爾值，表示某個(gè)鍵是否在當(dāng)前對(duì)象之中。 說(shuō)明 JavaScript數(shù)組去重這個(gè)問(wèn)題，經(jīng)常出現(xiàn)在面試題中，以前也寫(xiě)過(guò)一篇數(shù)組去重的文章，（JavaScript 數(shù)組去重的多種方法原理詳解）但感覺(jué)代碼還是有點(diǎn)不夠簡(jiǎn)單，今天和大家再說(shuō)兩種方法，代碼...
閱讀 1042·2021-09-30 09:58
閱讀 2878·2021-09-09 11:55
閱讀 2035·2021-09-01 11:41
閱讀 1021·2019-08-30 15:55
閱讀 3383·2019-08-30 12:50
閱讀 3528·2019-08-29 18:37
閱讀 3327·2019-08-29 16:37
閱讀 2042·2019-08-29 13:00
