每日挑战，从Javascript面试题目了解一些你可能忽略的概念 - Day28

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有基本认识

本文章同步发布於个人部落格，有兴趣的朋友也可以来逛逛~!