---
# System prepended metadata

title: Week 2

---

# Week 2

:::info
:::spoiler Click to Open TOC
[TOC]
:::

## Question
:::info
:::spoiler Click to Open Question
![](https://i.imgur.com/vlF5qh1.png)
### Check
- [x] Q1 Yee
- [x] Q2 chung
- [x] Q3 songchiu
- [x] Q4 Xian
- [x] Q5 songchiu
- [x] Q6 Mark
- [x] Q7 LXS
:::

## Answer
### Q1
> - [name=Yee]

![](https://i.imgur.com/k3h9i4m.png)

* #### Bubble sort

#### 【原理】

##### 以陣列實作泡沫排序法，從頭開始與下一個資料比較，若值較大則互相對調。

#### 【Stability】

##### 若比較時遇到值相等的資料，並不會做交換，因此泡沫排序法為stable。

#### 【In place】

##### 此演算法僅多使用一個變數的儲存空間(temp)，空間複雜度為$O(1)$，因此為in place的演算法。

:::spoiler english
##### Assume implements bubble sort in array,this sorting algorithm will change value with current index and next index step by step in the same array.

##### Therefore , the same value won't change it's original order so this sorting algorithm is stable.

##### Besides , this algorithm only use an integer(temp) for additional memory. The SpaceComplexity is $O(1)$ so it's a in place algorithm.

:::

##### 【程式碼】
```C=
BubbleSort(int arrays[],int array_length){
    for(int i=0;i<array_length-1;i++)
        for(int j=0;j<array_length-1;j++)
            if(arrays[j] > arrays[j+1]){
                int temp = arrays[j];
                arrays[j] = arrays[j+1];
                arrays[j+1] = temp;
            }
}
```




* #### Insertion sort
#### 【原理】
##### 以陣列實作插入排序法，首先令索引為$0$的資料為已排序好的數列(因為只有一筆資料)，再從索引為$1$的資料依序插入此數列。

#### 【Stability】

##### 若超過兩筆資料的值相同，因為插入排序好的數列是由最大的開始比較，若遇到相等的資料會停止迴圈，將後輸入的資料插入到其後，不會改變原先輸入的順序，所以插入排序法為stable。
#### 【In place】
##### 此演算法僅多使用一個變數的儲存空間(temp)，空間複雜度為$O(1)$，因此為in place的演算法。

#### 【程式碼】
``` C=
InsertionSort(int arrays[],int array_length){
    int j, i;
    for(i = 1; i <= array_length; i++){
        int temp = arrays[i];
        for(j = i; j > 0 && temp < arrays[j - 1]; j--)
            arrays[j] = arrays[j - 1];
        arrays[j] = temp;
    }
}

```

* #### Quick sort

#### 【原理】
##### 以陣列實作快速排序法，先選定陣列第一個資料為pivot，再將陣列分兩邊，左邊放比pivot小的資料，右邊則放比pivot大的資料。若左邊的資料大於pivot則與右邊資料交換，反之亦然。之後再將pivot與陣列中間的資料交換，使pivot放到正確的位置，並且將pivot前面的資料視為一陣列，pivot後面的資料視為另一陣列，再分別重新執行快速排序法。

#### 【Stability】

##### 當一開始的pivot放入正確位置時，且與pivot同值的資料超過兩個，有可能會使得與原先輸入的順序不同，因此快速排序法為unstable。
Ex : [1♠,1♥,5♥,2♥]  -> [1♥,1♠,2♥,5♥]


#### 【In place】

##### 此演算法使用遞迴多次呼叫自己，需使用到堆疊來存放，其空間複雜度取決於遞迴使用到的次數，每次先由所需遞迴次數少的開始，即可降低所需堆疊的空間，空間複雜度為$O(logn)$，因為 $logn$ 極小可視為常數，因此為in place的演算法。

#### 【程式碼】

``` C=
QuickSort(int arrays[],int left, int right){
    int i, j, pivot;
    if(left < right){
        i = left;
        j = right + 1;
        pivot = arrays[left];
        do{
            do
                i++;
            while(arrays[i] < pivot);
            do 
                j--;
            while(arrays[j] > pivot);
            if(i < j){
                int temp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = temp;
            }
        }while(i < j);
        int temp = arrays[left];
        arrays[left] = arrays[j];
        arrays[j] = temp;
        QuickSort(arrays,left,j - 1);
        QuickSort(arrays,j + 1,right);
    }
}
```

* #### Merge sort

#### 【原理】
##### 以陣列實作合併排序法，將原陣列不斷對半拆成兩陣列，直到只剩下一個資料，再將其排序並合併

#### 【Stability】

##### 若合併時遇到資料的值相同時，不會改變其輸入的順序，因此合併演算法為stable。


#### 【In place】

##### 此演算法除了使用遞迴多次呼叫自己，需使用到堆疊來存放，還需要再多一個陣列來存放，空間複雜度為$O(n)$，因此非in place的演算法。

#### 【程式碼】

``` C=
void MergeSort(int arrays[], int front, int end){                                        
    if (front < end) {                  
        int mid = (front + end)/2;         
        MergeSort(array, front, mid);    
        MergeSort(array, mid + 1, end);    
        Merge(array, front, mid, end);   
    }
}
```
* #### Heap sort

#### 【原理】
##### 以陣列實作二元樹，從最下面子樹的Parent, RightChild, LeftChild比較，使Parent大於另外兩節點，以此類推，即可建成Max Heap。再將Root與陣列最後方的資料交換，扣除陣列最後一個後(已排序)，再重新建成Max Heap。

#### 【Stability】

##### 若原輸入陣列即符合Max Heap，且Root的左子樹與右子樹為值相同的資料，最後排序完後將會交換位置，因此推疊演算法為unstable。
Ex [5♥,4♠,4♥,2♥]->[2♥,4♥,4♠,5♥]

#### 【In place】

##### 此演算法僅多使用一個變數的儲存空間(temp)，空間複雜度為$O(1)$，因此為in place的演算法。

#### 【程式碼】

``` C=
void HeapSort(int arrays[],int array_length){

    BuildMaxHeap(arrays);                                
    int size = array_length - 1;                    
    for (int i = array_length - 1; i >= 2; i--) {
        int temp = arrays[1];
        arrays[1] = arrays[i];
        arrays[i] = temp;
        size--;
        MaxHeapify(arrays, 1, size);                     
    }
}
```
### Q2
> - [name=chung]

![](https://i.imgur.com/c1lDDF8.png)


#### 【題目】
Design a data structure to represent a set with elements being positive integers, and then design algorithms for the following operations: 
Compute the union of two sets.
Compute the intersection of two sets. 
Determine if a given element is in a given set.


#### 【解題思維一】
本題需使用陣列，並且假設兩陣列皆已完成排序
1. Compute the union of two sets.
    - 由左至右比較兩陣列值的大小，並依序印出，考量兩陣列長度不一的狀況，若其中一陣列的元素已完全印出，則直接將另一陣列的值印出
    - worst case的情況兩陣列元素皆不同，需要遍歷所有元素，因此其時間複雜度為：O(m + n)
2. Compute the intersection of two sets.
    - 由左至右比較兩陣列值的大小，若兩陣列值相同則印出
    - worst case的情況兩陣列元素皆不同，需要遍歷所有元素，因此其時間複雜度為：O(m + n)
3. Determine if a given element is in a given set.
    - 需要遍歷所有元素，隨著n變大(linear search)，所花費的時間也增加的很快，因此其時間複雜度為： O(n)

#### 【程式碼一】
```cpp=
// Compute the union of two sets.
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
void printUnion(int arr1[], int arr2[], int m, int n)
{
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            cout << arr1[i++] << " ";
 
        else if (arr2[j] < arr1[i])
            cout << arr2[j++] << " ";
 
        else {
            cout << arr2[j++] << " ";
            i++;
        }
    }
 
    while (i < m)
        cout << arr1[i++] << " ";
 
    while (j < n)
        cout << arr2[j++] << " ";
}
```

```cpp=
// Compute the intersection of two sets. 
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
void printIntersection(int arr1[], int arr2[], int m, int n)
{
    int i = 0, j = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]){
            i++;
        }
        else if (arr2[j] < arr1[i]){
            j++;
        }
        else
        {
            cout << arr2[j] << " ";
            i++;
            j++;
        }
    }
}
```

```cpp=
// Determine if a given element is in a given set.
// e is the given element
bool findElement(int arr[], int e){
 
    for (int i = 0; i < arr.length; i++){
        if (arr[i] == e) {
            return true;
        } else {
            return false;
        }
    }
}
```

#### 【解題思維二】
C++ std::set 是一個關聯式容器，set容器裡面的元素是唯一的，具有不重複的特性，並且在插入元素的同時會根據元素來進行排序。
1. Compute the union of two sets.
    - set容器中具有元素不重複的特性，因此將兩陣列元素插入set容器中並依序印出，即可取得聯集
    - 考量worst case的情況兩組set的數字都不同，需要遍歷所有元素，因此其時間複雜度為：O(m + n)

3. Compute the intersection of two sets.
    - 將一陣列插入至set容器，並比對陣列二中的元素，取出相同元素即可得到結果
    - 考量worst case的情況兩組set的數字都不同，需要遍歷所有元素，因此其時間複雜度為：O(m + n)

4. Determine if a given element is in a given set.
    - 將陣列插入至set容器，並使用 find() 成員函式來判斷指定元素是否存在於set當中
    - 執行一次find平均花費的時間，隨著n變大(linear search)，增加的很快，因此其時間複雜度為： O(n)

#### 【程式碼二】
```cpp=
// Compute the union of two sets.
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
void printUnion(int arr1[], int arr2[], int m, int n)
{
    set<int> unionSet;
    
    for (int i = 0; i < m; i++){
        unionSet.insert(arr1[i]);
    }
 
    for (int i = 0; i < n; i++){
        unionSet.insert(arr2[i]);
    }
    for (auto it = unionSet.begin(); it != unionSet.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
}
```

```cpp=
// Compute the intersection of two sets. 
// m is the number of elements in arr1[]
// n is the number of elements in arr2[]
void printIntersection(int arr1[], int arr2[], int m, int n)
{
    set<int> intersectionSet;
 
    for (int i = 0; i < m; i++)
        intersectionSet.insert(arr1[i]);
 
    for (int i = 0; i < n; i++)
        if (intersectionSet.find(arr2[i]) != intersectionSet.end())
            cout << arr2[i] << " ";
}
```

```cpp=
// Determine if a given element is in a given set.
// e is the given element
bool findElement(int arr[], int e){
    set<int> searchSet;
 
    for (int i = 0; i < m; i++)
        searchSet.insert(arr[i]);
    
    auto search = searchSet.find(e);
    
    if (search != searchSet.end()) {
        return true;
    } else {
        return false;
    }
}
```

$\;$

### Q3
> - [name=songchiu]

![](https://i.imgur.com/5JBK6Vo.png)
#### 【想法】
- 兩陣列已排序過，當index上升時，其value也會上升
- 固定其中一個陣列的index，去與另一個陣列的元素進行比較，使兩邊value的差值持續縮小
- 不停的試即可找出答案

#### 【時間複雜度】
考量worst case差值最小的情況皆在兩陣列的最末端，其時間複雜度為：$O(m+n)$

#### 【程式碼】
```cpp=
int min=INT_MAX, x_index=0, y_index=0;
while(x_index < m AND y_index < n)
{
    int temp = abs(x[x_index] - y[y_index]);
    if(temp < min)
        min = temp;

    if(x[x_index] < y[y_index])
        x_index++;
    else
        y_index++;
}
cout << min << endl;
```

$\;$

### Q4
> - [name=Xian]

![](https://i.imgur.com/AC5lBnN.png)
#### 【題目】
Solve the recurrence $T(n) = 2T(\dfrac{n}{2}) + n\ – 1$ where $n = 2^𝑘$ is assumed. $T(1)=0.$
#### 【解1-證明】
$\begin{aligned}
T(n) &= 2\ T(\dfrac{n}{2})+n-1\\
     &= n-1+2(2\ T(\dfrac{n}{4})+\dfrac{n}{2}-1)\\
     &= n-1+n-2+4\ T(\dfrac{n}{4})\\
     &= n-1+n-2+4(2\ T(\dfrac{n}{8})+\dfrac{n}{4}-1)\\
     &= n-1+n-2+n-4+8\ T(\dfrac{n}{8})\\
     &= \cdots\\
     &= n-1+n-2+\cdots+n-2^{k-1}+2^k\ T(\dfrac{n}{2^k})\\
     &= n-1+n-2+\cdots+n-2^{k-1}+n\ T(1)\\
     &= kn-(1+2+\cdots+2^{k-1})\\
     &= kn-2^k+1  \quad (n = 2^k,k = \log_{2}{n})\\
     &= n\log_{2}{n}-2^{\log_{2}{n}}+1\\
     &= n\log_{2}{n}-n+1\\
     &= {\Theta(n\log_{2}{n})}_\#
\end{aligned}$

#### 【解2】
>solved by Master Thoerem.

$a=2,b=2,c=1$
$\because a = b^c \iff\dfrac{a}{b^c} = 1$
$\therefore T(n)= \Theta (n^c\log_{b}{n})=\Theta(n^1\log_{2}{n}) = \Theta(n\log_{2}{n})_\#$

### Q5
> - [name=songchiu]

![](https://i.imgur.com/PFny4GF.png)

#### 【想法 - A小題】
- 先透過MergeSort來將資料排序
- 設定兩個指標分別指向S的頭尾，透過夾擊的方式來計算兩數之和
- 相加的情況：
  - 頭+尾 > 目標，尾巴指標-1
  - 頭+尾 < 目標，開頭指標+1
  - 頭+尾 = 目標，已找到
- 若兩指標相遇，仍未找到答案，則回傳false
- 這樣的時間複雜度就只有MergeSort的$O(n \; log \; n)$+兩邊夾擊的worst case $O(n)=O(n \; log \; n)$，會比題目原先所述的$O(n^2)$來的好

#### 【程式碼 - A小題】
```cpp=
bool twoSum(int S[], int n, int target)
{
    mergeSort(S);
    
    int front=0, back=n-1, temp_sum;
    while(front < back)
    {
        temp_sum = S[front]+S[back];
        if(temp_sum > target)
            back--;
        else if(temp_sum < target)
            front++;
        else
            return true;
    }
    
    return false;
}
```

#### 【想法 - B小題】
- 先將資料透過MergeSort進行排序
- 採取A小題前後夾擊之方式，並且再透過二分搜尋法的概念，找取三數的中間項
- 時間複雜度為MergeSort的$O(n \; log \; n)$+前後夾擊&二分搜尋的$O(n \; log \; n)=O(n \; log \; n)$

#### 【程式碼 - B小題】
```cpp=
bool threeSum(int S[], int n, int M)
{
    mergeSort(S);
    
    int front=0, back=n-1;
    
    while(front < back)
    {
        if(S[front] + S[back] > M)
            back--;
        else
        {
            if(binarySearch(S, front+1, back-1, M - S[front] - S[back]))
                return true;
            else
                front++;
        }
    }
    
    return false;
}
```
註：`binarySearch`會回傳`True` or `False`

#### 【想法 - C小題】
- 由於k無法確定大小，採取dp來解決此問題
- 讓$dp[a][b][c]$代表著，從前$a$個數字取$b$個數字，看能否加總出$c$
- 最後的結果，可以在$dp[n][k][M]$當中找到
- 時間複雜度為$O(nkM)$

#### 【遞迴式 - C小題】
$DP[a,b,c]=
\begin{cases}  
true  & \mbox{if }b、c = 0 \\ 
or\{ DP[a-1,b,c],\;DP[a-1,b-1,c-S_i]\}  & \mbox{if }c - S_a \geq 0\ (應該是or才對吧??)\\ 
DP[a-1,b,c] & \mbox{otherwise} 
\end{cases}$

#### 【程式碼 - C小題】
```cpp=
bool kSum(int S[], int n, int M, int k)
{
    bool dp[n+1][k+1][M+1] = {false};
    
    for(int i=0; i<=n; i++)
        dp[i][0][0] = true; //取0個數字可以加總出0
        
    for(int a=1; a<=n; a++)
    {
        for(int b=1; b<=k && b<=a; b++)
        {
            for(int c=M; c>=1; c--)
            {
                if(c-S[a] >= 0)
                    dp[a][b][c] = dp[a-1][b][c] || dp[a-1][b-1][c-S[a]];
                else
                    dp[a][b][c] = dp[a-1][b][c];
            }
        }
    }
    
    return dp[n][k][M];
}
```

$\;$

:::spoiler 舊版
#### 【想法 - A小題】
- 透過取餘數的方式，將餘數建成一張表
- 透過該表，來快速配對，找出目標值$M$
- 所花的時間為：建立餘數表$O(M)$+計算餘數表$O(n)$+找有沒有符合的答案$O(\dfrac{M}{2})$
- 因此時間複雜度是$O(n+M)$

#### 【程式碼 - A小題】
```cpp=
bool twoSum(int S[], int n, int M)
{
    int i, remainder[M];
    
    for(i=0; i<M; i++)
        remainder[i] = 0; //initialize
    
    for(i=0; i<n; i++)
        if(S[i] < M)
            remainder[S[i] % M]++; //計算餘數表
    
    for(i=0; i<M/2; i++)
        if(remainder[i] > 0 && remainder[M-i] > 0)
            return true;
    
    if(i >= M/2) 
    {
        //處理餘數表剛好在中間的case
        //例如：S[]={1, 2, 3, 6, 7}，M=12 or 13時，即需要此段程式碼
        if(M % 2 == 0 && remainder[M/2] > 1)
            return true; //兩個相等的數相加起來為M
        else if(M % 2 != 0 && remainder[M/2] > 0 && remainder[M - M/2] > 0)
            return true;
    }
    
    return false;
}
```

#### 【想法 - B小題】
- 先將陣列S進行排序(為降低時間複雜度，採取Merge Sort)
- 與[Q3](###Q3)想法類似，採取前後夾擊之方式，並且再透過二分搜尋法的概念，找取三數的中間項
- 時間複雜度為Merge Sort的$O(n \; log \; n)$ + 前後夾擊&二分搜尋的$O(n \; log \; n)$ = $O(n \; log \; n)$


#### 【程式碼 - B小題】
```cpp=
bool threeSum(int S[], int n, int M)
{
    MergeSort(S);
    
    int front=0, back=n-1;
    
    while(front < back)
    {
        if(S[front] + S[back] > M)
            back--;
        else
        {
            if(binarySearch(S, front+1, back-1, M - S[front] - S[back]))
                return true;
            else
                front++;
        }
    }
    
    return false;
}
```
:::

<!-- 歡迎回來 -->
<!-- 早啊 -->

### Q6
> - [name=Mark]

[LeetCode 23. Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)
![](https://i.imgur.com/Rbe9xcH.png)

#### 題目
**Merge K Sorted Lists, and Excutation Time of the Algorithm.**
#### 解題思路
- 由於是 Sorted List，我們只需按順序從 List Head 挑出最小放入即可
- 同一梯次比較的順序不重要，只要找出最小的 **$\rightarrow$ MinHeap!!**
#### 步驟
- 將所有 Lists 的第一個元素放到 MinHeap
- Pop 出最小的
- 被 Pop 的元素 Pointer 指向 Next，重新 Insert 回去
- 直到所有元素 Pop 完
#### Pseudo Code
```cpp=
func mergeKLists(Lists, K)
{
    MinHeap = generateMinHeap(K);

    for(let i from 0 to K) do
        insert(MinHeap, Lists[i]);

    let Head = new List;
    let Cursor = Head;

    while(MinHeap)
    {
        let Current = extractMinHeap();
        if(Current->next) insert(MinHeap, Current->next);
        Cursor->next = Current;
        Cursor = Cursor->next;
    }
    
    return Head->next;
}
```
:::spoiler 程式碼 implement in Cpp
```cpp=
/**
 * Definition for singly-linked list.
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // min priority queue
        auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
        
        for(int i = 0; i < lists.size(); i++)
            if(lists[i] != nullptr) 
                q.push(lists[i]);
        ListNode* dummy = new ListNode(0);
        ListNode* cursor = dummy;
        while(!q.empty()){
            ListNode* curr = q.top();
            q.pop();
            if(curr->next != nullptr) q.push(curr->next);
            cursor->next = curr;
            cursor = cursor->next;
        }
        return dummy->next;
    }
};
```
:::

#### Time Complexity
$O(Nlog{K})$
- MinHeap 的 Insert & Pop $O()=logN$(在本題為K)
- 全部共 N 個 Node，故總時間複雜度為$O(Nlog{K})$

Ref. [Use MinHeap to Solve Merge K Sorted Lists](https://www.youtube.com/watch?v=ptYUCjfNhJY)

<!--  你的車車還好嗎
> 被無情拖吊QQ
> 拖吊+紅單共兩千
> \\|/
> 我以為週末拖吊車不會上班
> 這碗鮮芋仙還真貴啊… -->

### Q7
> - [name=LXS]

![](https://i.imgur.com/bgkP2bQ.png)

#### 【解題思路】

使用一自平衡二元搜尋樹 (AVL、紅黑數)，每個節點包含輸入之相異整數與對應數量
由於每個節點都是相異數字$\rightarrow$最多$O(\log n)$個節點$\rightarrow$樹高$O(\log\log n)$

#### 【A小題】
輸入**n**個整數，每次輸入對二元樹進行一次搜尋
* 對於新元素，插入新結點
* 對於存在的元素，對節點的數量+1

兩者時間複雜度皆為$O(\log N)$，其中$N$為樹中節點數
由於可以保證樹內的節點數**N**$<O(logn)$
因此每次輸入在最壞情形下需要$O(\log\log n)$
一共有n個輸入因此建樹時間為$O(n\log\log n)$

我們對二元樹進行一次 Inorder Traversal 即可得到排序後的結果，此步相對Trivial
遍歷節點時間複雜度為$O(\log n)$，依照次數重複輸出，時間複雜度為$O(n)$

Note: 空間複雜度$O(n)$

#### 【B小題】
$\Omega(n\log n)$是基於每個輸入皆相異的比較排序的下限，由於序列中不同元素的數量為$O(\log n)$且有重複
而我們只對樹中相異元素做比較，因此$\Omega(n\log n)$不適用此情形。

::: spoiler C++ Code

> 一般而言STL中map使用紅黑樹實作
> `myMap[key]++` 當key不存在時做Insert(key, 0)，存在時將value++

```cpp=
#include <iostream>
#include <map>

int main()
{
    std::map<int, int> myMap;

    int arr[] = { 1, 1, 2, 1, 1, 3, 4, 3, 1, 1, 2, 1, 1, 3, 4, 3 };
    
    for (auto key : arr) {
        myMap[key]++;
    }

    for (auto i : myMap)
        for(auto j=0; j<i.second; j++)
            std::cout << i.first;
}
```
:::