# 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; } ``` :::