Map
如果想要了解 Map() 的特性,建議可以參考 PJ 大大的這篇文章,整理得超好,一開始看MDN的文件我觀察一段時間才比較清楚要怎麼使用。
以 LeetCode 169. Majority Element 這題為例,要計算出現次數超過陣列長度一半的數字(假設陣列不為空),可以這樣運用 Map:
var majorityElement = function(nums) {
let timeRecord = new Map()
let half = nums.length / 2
for (let i = 0; i < nums.length; i++) {
if (!timeRecord.has(nums[i])) {
timeRecord.set(nums[i],1)
} else {
timeRecord.set(nums[i], timeRecord.get(nums[i])+1)
}
}
for (let [key, value] of timeRecord) {
if (value >= half) return key
}
};
Map 是類似於 object 的 key-value pair,在適當的情況下,運用起來彈性更大、效能更好,像是它的 key 可以是任何值且具備唯一性等等。
在上面這段程式碼中,首先建立了一個空 Map,接著於迴圈當中用 has( ) 判斷我的 Map 鍵裡面有沒有當前的 nums[i],如果沒有就用 set( ) 添加並且記錄這個數字出現 1 次;如果 Map 裡面已經存在數字,就用 get( ) 取出 value 並加 1,最後會得到一個計算每個數字出現次數的 Map,然後在利用 for of 遍歷搭配判斷式回傳 value 大於陣列長度一半的那個數字。
當然也有其他人的解法相當簡潔:
var majorityElement = function(nums) {
let majorMap = {};
nums.forEach(i => {
if (majorMap[i]) {
majorMap[i] += 1
} else {
majorMap[i] = 1;
}
})
return Object.entries(majorMap).sort((a,b) => b[1] - a[1])[0][0] };
這段程式碼當中的 Object.entries( ) 也是個比較少見的用法,如果把它拿來跟 Object.values( ) 比較,整個概念會容易理解一些:
Input: var object = { 0: '23', 1: 'geeksforgeeks', 2: 'true' };
console.log(Object.values(object));
console.log(Object.entries(object));
Output: Array ["23", "geeksforgeeks", "true"]
Array [["0", "23"], ["1", "geeksforgeeks"],["2", "true"]]
它跟 Array.prototype.entries( ) 也是不太一樣的:
Input: const array1 = ['a', 'b', 'c'];
const iterator1 = array1.entries(); console.log(iterator1.next());
console.log(iterator1.next().value);output: Object { value: Array [0, "a"], done: false }
Array [1, "b"]
這個方法會回傳一個 Iterator
物件,是包含了插入順序的陣列,其中的 done 屬性代表的是這個 Iterator
是否還能生成下一個值,也就是說如果 next( ) 跑完、沒有下一個 value 了,done 將回傳 true。(不知道可以用在什麼地方xddd)
注:JS 中的 sort 運用的是時間複雜度為 O(n log n) 的 merge sort 。
後來在留言處 Schaos 提醒了大家,其實 Array.prototype.sort 在 ECMA 規範 中並沒有指定預設的排序實作方式,因此 JavaScript 中的排序方式其實是看各家瀏覽器如何實作。
Set
以 LeetCode 217. Contains Duplicate 為例,要判斷傳入的陣列中是否包含重複值:
var containsDuplicate = function(nums) {
const array = new Set(nums)
return array.size < nums.length
}
Set 可以視為一個 values 的收集器,每個值只會出現一次而已,所以特別適合運用在去除陣列中的重複值。
以上這段程式碼中,只是比較了已經去除重複值的 array 跟原本 nums 的長度,就可以得出答案了。
Set 也具備像 add( )、delete( )、has( )、size 等方法,更多資訊可以參考這篇在 JAVASCRIPT.INFO 上的文章。
以上是簡單的筆記,文章中有什麼錯誤還請多多指教,如果對你有幫助的話也歡迎拍拍手哦。