JS中的 Set() 與 Map()

還有平常少見的的冷門語法。

Walle

Published in

漫築蘭格

5 min readDec 10, 2019

由於參加了 Alpha Camp 舉辦的 CS 工作坊，再加上寫畢業考的關係，最近有比較頻繁地在 LeetCode 上解題，也因此看見了許多五花八門的演算法，有些語法的運用方式稍微難記了點，特此筆記。

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 上的文章。

以上是簡單的筆記，文章中有什麼錯誤還請多多指教，如果對你有幫助的話也歡迎拍拍手哦。

JS中的 Set() 與 Map()

還有平常少見的的冷門語法。

Map

Set

Written by Walle