---
tags: 讀書會
---

## 資料結構與演算法搭配 Leetcode Day Final (8/28)

### 今天來不及準備 leetcode 但是學到的技巧可以解滿多題的

---

補充 & 溫故知新

1. O(n^2) 以上是辣雞扣

---

## 延續前章： Introduction to Algorithm Design
>演算法設計導論

這章節會學習到演算法與資料結構課程的核心 學習好幾個有用的演算法及談到他們設計原理

上次已經談過最簡單的 Linear Search 跟 Binary Search，本節來談另外兩個好用的小技巧 Counter 跟 Pointer！

1. Linear Search 線性搜索

2. Binary Search 二分搜尋法

3. Counter

4. Pointer

5. Sliding Window 滑行的視窗，有名的演算法

6. Recursion 遞迴

---

為甚麼需要這兩個小技巧呢？

=> 當然是為了減少時間複雜度

---

## General Guide of Algorithm Design
>演算法中的一般性指南

在介紹演算法中的重要技巧 Counter 和 Pointer 之前
先來介紹在演算法中的一般性指南

當你在寫演算法之前，請先思考要如何設計它
先在腦中思考好，不要先讓電腦做愚蠢的事情

愚蠢的事情 => 超大的時間複雜度

---

## Intersection Problem
>交集問題

將兩個 arr 交集的 element 抓出來回傳成新的 arr。

input:
arr1 = [1, 2, 3] 
arr2 = [5, 16, 1, 3]

output:
[1, 3]

大家會怎麼解決呢？

---

最直覺的會用雙層迴圈來解決

大概會像這樣：

function intersection(arr1, arr2) {
  let result = []
  for (let i = 0; i < arr1.length; i++) {
    for (let j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) {
        result.push(arr2[j])
      }
  }
  }
  if (result.length === 0 ) {
    return -1
  } else {
    return result
  }
}

---

### 來看時間複雜度

可以來想一下這樣做的時間複雜度

因為是雙層迴圈，所以時間複雜度就是 `O(n^2)` 或是說 `O(n*m)`

**辣雞扣！**

接下來我們就要學 Counter 的技巧

將複雜度從 O(n^2) 簡化成 O(n)

---

## Counter

- 是個很常見的技巧，在做演算法設計（algorithm design）的時候很常用到，這邊是用交集來舉例

- 不是正式的名字，是我們課堂上的老師取的，所以各路人馬的命名會不太一樣，這邊主要學他的概念及思路

- 使用方式：建立 Counter object 來降低演算法的複雜度

---

### Counter 的思路
>來數ㄕㄨˇ數ㄕㄨˋ吧！

建立一個新的 counter object，在裡面存取各 element 共出現幾次，最後再來把出現一次以上的列出。

建立一個新的物件：counter object，裡面紀錄兩個陣列中全部的數字出現的數量。

input:
arr1 = [1, 2, 3] 
arr2 = [5, 16, 1, 3]

counter = {
	1: 2,	// 1 出現 2 次
	2: 1,	// 2 出現 1 次...
	3: 2,
	5: 1,
	16: 1
}

//我們只要把 value 大於 1 的 key 值抓出來就是答案

output:
[1, 3]

新建立一個 counter object 就是 counter 的精神

---

### 中文ㄉ Pseudocode for Counter
ㄉ
1. 將兩個陣列合併，建立 counter object

2. 遍歷新陣列，將裡面的元素出現的次數記錄在 counter object 內

3. 遍歷 counter object，將出現 1 次以上的 key 挑出來就是答案

---

### 實作 Counter 程式碼

- 合併陣列 concat() ，此方法會回傳新陣列，不會影響原陣列[concat()](https://developer.mozilla.org/zh-TW/docs/Web/JavaScript/Reference/Global_Objects/Array/concat)

function intersection(arr1, arr2) {
  let result = []
  let arr3 = arr1.concat(arr2)
  let counter = {}

  for (let i = 0; i<arr3.length; i++) {
    if (!counter[arr3[i]]) {
      counter[arr3[i]] = 1
    } else {
      counter[arr3[i]]++
    }
  }

  for (let value in counter) {
    if (counter[value] > 1) [
      result.push(value)
    ]
  }

  return result
}

---

### 來看 Counter 時間複雜度

我們只是把兩個陣列都 run 過一次，所以複雜度就是 O(n+m) 也可以寫

剛剛雙層迴圈的作法複雜度就是 `O(n*m)` ，現在簡化成 `O(n+m)`

是不是很方便呢～

---

下面介紹 Pointer

## Coding Practice - Average Pair
>平均對問題

指定一個**數字**及一個 **sorted array** ，目的是在 sorted array 中找到任何成對的數字，這成對的數字的平均值要等於指定的數字。

input: [-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5

output: [ [ 14, -11 ], [ 3, 0 ], [ 2, 1 ] ]

averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

大家會怎麼解決呢？

---

最直覺的會用雙層迴圈來解決

### 來看時間複雜度

可以來想一下這樣做的時間複雜度

因為是雙層迴圈，所以時間複雜度就是 `O(n^2)` 或是說 `O(n*m)`

**辣雞扣！**

接下來我們就要學 Pointer 的技巧

將複雜度從 O(n^2) 簡化成 O(n)

---

## Pointer

- 是個很常見的技巧，在做 sorted array 演算法設計（algorithm design）的時候很常用到

- 不是正式的名字，是我們課堂上的老師取的，所以各路人馬的命名會不太一樣，這邊主要學他的概念及思路

- 使用方式：使用兩個左右兩個箭頭(Pointer)，來降低演算法的複雜度

---

### Pseudocode for Pointer

function averagePair(arr, avg) {
	let left = 0	
	let right = arr.length - 1
	let result = []

	while (right > left) { // 一小於就停止，因為是 sorted array
		let 目前平均 = (左邊 point + 右邊 point) / 2
		if 目前平均 > 指定數字 => right - 1
		else if 目前平均 < 指定數字 => left + 1
		else if 目前平均 = 指定數字 => result.push([arr[left], arr[right]])
															 	 right -1 , left +1
	}

	return result
}

// avg 平均的意思

### 實作 Pointer 程式碼

averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5);

function averagePair(arr, avg) {
  let left = 0
  let right = arr.length -1
  let result = []

  while (right > left) {
    let temp_avg = (arr[left] + arr[right]) /2
    if (temp_avg > avg) {
      right --
    } else if (temp_avg < avg) {
      left ++
    } else if (temp_avg === avg) {  // 忘記的是小狗
      result.push([arr[left], arr[right]])
      right --
      left ++
    }
  }

  console.log('result = ', result)
}

### Pointer 時間複雜度

只會用一個 for loop run 一遍 array

- 所以時間複雜度是 O(n)

是不是很方便呢？

---

### 演算法讀書會到此結束

要探討演算法與資料結構的核心，必須先具備以下六種常見演算法的知識，了解這些常用的演算法的設計原理。

目前已經學了前四個

1. Linear Search 線性搜索

2. Binary Search 二分搜尋法

3. Counter - Counter object

4. Pointer - right left 箭頭

之後兩個也很重要，一個是很有名的演算法滑窗，另一個是要腦袋轉彎的遞迴

5. Sliding Window 滑行的視窗，有名的演算法

6. Recursion 遞迴

如果想要加入演算法的行列請點選以下購買連結～

購買連結：

[Udemy 資料結構與演算法 (JavaScript)](https://www.udemy.com/course/algorithm-data-structure/)

---

## 謝謝大家，希望未來還有機會可以一起辦讀書會

## 最後一個多月，衝呀～