[演算法] Harmless Ransom Note：計算陣列中各元素出現的次數
keywords: hash table, important
計算陣列中各元素出現的次數（calculate the number of elements in an array）
問題描述
這是一個類似單字剪報功能的演算法，告訴它我們希望得到哪些單字（noteText），然後在一篇文章（magazineText）中去尋找看看能不能找到這些單字，而且數量要足夠。
因此要寫一個 harmlessRansomNote function，並且代入兩個參數 noteText 和 magazineText，如果 noteText 中的單字和數量都能在 magazineText 中被找到，則回傳 true，否則回傳 false。
// return true/false
function harmlessRansomNote (noteText, magazineText) {...}
前置知識
判斷演算法的好壞：Big O Notation & Time Complexity @ PJCHENder HackMD
演算法實做
步驟一：將輸入的字串改成陣列
我們可以使用 Array.prototype.split 這個方法來將計算拆成陣列：
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
let noteArr = noteText.split(' ');
let magazineArr = magazineText.split(' ');
}
步驟二：計算陣列中各元素的次數
接著我們要計算在 magazineArr 中共有哪些單字，且每個單字出現幾次：
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
/* ... */
// 以物件的方式儲存每個單字出現的次數
let magazineObj = {};
magazineArr.forEach((word) => {
// 如果這個單字還沒出現在 `magazineObj` 過，則建立它
if (!magazineObj[word]) magazineObj[word] = 0;
// 讓這個字的出現次數多 1
magazineObj[word]++;
});
}
步驟三：檢查 noteText 中的單字和數量是否在 magazineText 中足夠
當 noteText 裡的單字能夠在 magazineObj 中被找到時，而且該單字還有數量時（>0），則把 magazineObj 中的該單字減 1；否則表示沒有該單字或數量不足（noteIsPossible = false）
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
/* ... */
// 以物件的方式儲存每個單字出現的次數
/* ... */
// 檢查 noteText 中的單字和數量是否在 magazineText 中足夠
let noteIsPossible = true;
noteArr.forEach((word) => {
if (magazineObj[word] > 0) {
magazineObj[word]--;
} else {
noteIsPossible = false;
}
});
return noteIsPossible;
}
程式示範
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
let noteArr = noteText.split(' ');
let magazineArr = magazineText.split(' ');
// 以物件的方式儲存每個單字出現的次數
let magazineObj = {};
magazineArr.forEach((word) => {
if (!magazineObj[word]) magazineObj[word] = 0;
magazineObj[word]++;
});
// 檢查 noteText 中的單字和數量是否在 magazineText 中足夠
let noteIsPossible = true;
noteArr.forEach((word) => {
if (magazineObj[word] > 0) {
magazineObj[word]--;
} else {
noteIsPossible = false;
}
});
return noteIsPossible;
}
let noteText1 = 'This magazine magazine';
let noteText2 = 'This magazine magazine magazine';
let magazineText = 'This is all the magazine text in the magazine';
console.log(harmlessRansomNote(noteText1, magazineText)); // true
console.log(harmlessRansomNote(noteText2, magazineText)); // false（"magazine" 數量不足）
- Algorithm: Harmless Ransom Note @ Repl.it
Time Complexity
根據最前面提到的 Big O Notation 的說明，可以看到剛剛寫得這個演算法大概可以分成兩個部分：
第一個是 magazineArr.forEach(...) ，當 magazineArr 中的元素越多的時候，執行速度會等比例的增加，因此屬於 Linear Time Complexity (Big O(n))。
第二個是 noteArr.forEach(...) ，當 noteArr 中的元素越多的時候，執行速度會等比例的增加，因此同樣屬於 Linear Time Complexity (Big O(n))。
當一個函式中有兩個 Big O(n) 時，表示 O(n) + O(m)，可以寫成 O(n + m)，因為是線性相加，所以可以表示一樣可以用 O(n) 表示。
補充：使用 Map 製作 HashTable
// Credits: Engine Lin (https://medium.com/@linengine)
const arr = [
'apple',
'apple',
'banana',
'banana',
'cat',
'dog',
'fat',
'fat',
'fat',
'fat',
];
const hashTable = new Map();
arr.forEach((item) => {
if (hashTable.has(item)) {
hashTable.set(item, hashTable.get(item) + 1);
} else {
hashTable.set(item, 1);
}
});
// Map { 'apple' => 2, 'banana' => 2, 'cat' => 1, 'dog' => 1, 'fat' => 4 }
console.log(hashTable);