2017年9月22日

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

      , ,  

計算陣列中各元素出現的次數（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" 數量不足）

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) 表示。

資料來源

0 意見:

張貼留言