tags: ItIron2021 Javascript

前言

昨天我們跑了一個本系列最~簡單的題目之一，想必應該有好好放鬆到吧! 那今天就稍微把難度再拉回來一點吧! 馬上來看一下之前在外商面試時遇到的一個題目吧!

本日題目與解釋

今有兩unique陣列，請說明你要如何找出兩陣列中重複的元素

當你連續被騙了好幾次後，我想你這次學乖了，你要先釐清問題。因此你的第一個問題應該是什麼是unique陣列? 很好的問題，這也是當時我第一個問的問題，第一次面試又是英文，聽到unique array我整個傻了一下?

面試官接著定義了所謂的unique陣列，也就是陣列中本身就沒有任何重複的元素，同時她還加了一個條件讓事情更簡單，這兩個陣列中都只有數字，最後請以陣列的方式回傳結果，好了，請作答!

這個問題同樣有著非常多的解法，我們就隨便講一個吧!

• 隨便想的解法: loop

我絕對不是在複製貼上..不過當你沒招時從最基本想就對了! 我們可以用以下的思路配合迴圈解這一道題目

迭代陣列1或陣列2，若裡面有與另一個陣列重複的元素便將該元素推進結果陣列

為了方便我說明，我們先假設兩陣列為以下

const arr1 = [1, 5, 8, 9, 10, 11, 17]
const arr2 = [1, 2, 17, 23, 28, 32]

範例有了、基本想法也有了，那就用for loop寫看看吧!

const result = []

for (let i = 0; i < arr1.length; i++) {
  if (arr2.includes(arr1[i])) {
    result.push(arr1[i])
  }
}

console.log(result) // [1, 17]

同樣的概念你也可以用ES6之後的語法糖來寫，.filter一樣可以把任務完成得很漂亮

const result = arr1.filter(num => arr2.includes(num))

console.log(result) // [1, 17]

好了，現在題目回答完畢了，面試官問了你下一個問題

那請問你這個解法的時間複雜度是?

嘿嘿，成功帶到我今天想談的概念之一了，計畫通?

當你回答這類演算法的題目時，其實有不少的人會開始關心起所謂的Big O Notation & Time Complexity，簡單來說就是衡量你演算法效能的一種指標，簡易的說明你的解法在最壞情況下(也就是資料量變大的時候)的表現，大致上分為以下的4種類型

• Constant Run Time (O(1)) 程式碼的執行時間不會隨著處理的資料量變大而遞增
• Linear Run Time (O(n)) 程式碼的執行時間隨著資料量變大呈現線性的遞增關係
• Logarithmic Run Time (O(log n)) 程式碼的執行時間隨著資料量變大而增加，但隨著資料量越大，增加的幅度越趨緩
• Exponential Run Time (O(n^2)) 程式碼的執行時間隨著資料量變大呈現指數型的成長關係

一般來說我們會試著避免最後一種指數型的情況，如果以上的內容你完全沒有任何概念或是覺得看了天書，那請利用今天提供的關鍵字去做基本的了解並學會如何計算你的演算法時間複雜度!

順帶一題，由於跑了雙迴圈，我們這個解法的時間複雜度很遺憾的為O(n^2)。

以下附上我當時給的O(n)解法，但當時我實在太緊張，講得零零落落的XD

const result = []
const DIC = {}
for (let i = 0; i < arr1.length; i++) {
  // 統計在arr1出現過的數字
  DIC[arr1[i]] = 1
}

for (let i = 0; i < arr2.length; i++) {
  // 若跑到的數字已存在DIC，表示重複，推到結果陣列
  if (DIC[arr2[i]]) {
     result.push(arr2[i])
  } 
}

console.log(result) // [1, 17]

本日核心觀念與總結

核心觀念

Big O Notation & Time Complexity

總結

• 對於Big O Notation & Time Complexity有基本認識

本文章同步發布於個人部落格，有興趣的朋友也可以來逛逛~!