2017年9月22日 星期五

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

計算陣列中各元素出現的次數(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) 表示。

資料來源

0 意見:

張貼留言