Skip to main content

[演算法] Harmless Ransom Note:計算陣列中各元素出現的次數

keywords: hash table, important#

計算陣列中各元素出現的次數(calculate the number of elements in an array)#

問題描述#

這是一個類似單字剪報功能的演算法,告訴它我們希望得到哪些單字(noteText),然後在一篇文章(magazineText)中去尋找看看能不能找到這些單字,而且數量要足夠。

因此要寫一個 harmlessRansomNote function,並且代入兩個參數 noteTextmagazineText,如果 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" 數量不足)

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);

資料來源#

Last updated on