PJCHENder 未整理筆記

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

2017-09-26

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

keywords: hash table, important

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

問題描述

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

因此要寫一個 harmlessRansomNote function,並且代入兩個參數 noteTextmagazineText,如果 noteText 中的單字和數量都能在 magazineText 中被找到,則回傳 true,否則回傳 false。

1
2
// return true/false
function harmlessRansomNote (noteText, magazineText) {...}

前置知識

判斷演算法的好壞:Big O Notation & Time Complexity @ PJCHENder HackMD

演算法實做

步驟一:將輸入的字串改成陣列

我們可以使用 Array.prototype.split 這個方法來將計算拆成陣列:

1
2
3
4
5
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
let noteArr = noteText.split(' ');
let magazineArr = magazineText.split(' ');
}

步驟二:計算陣列中各元素的次數

接著我們要計算在 magazineArr 中共有哪些單字,且每個單字出現幾次:

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function harmlessRansomNote(noteText, magazineText) {
// 將輸入的資料轉成陣列
/* ... */

// 以物件的方式儲存每個單字出現的次數
/* ... */

// 檢查 noteText 中的單字和數量是否在 magazineText 中足夠
let noteIsPossible = true;
noteArr.forEach((word) => {
if (magazineObj[word] > 0) {
magazineObj[word]--;
} else {
noteIsPossible = false;
}
});
return noteIsPossible;
}

程式示範

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 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);

資料來源

掃描二維條碼,分享此文章