算法初步——two pointers
什么是 two?pointers
以一個例子引入:給定一個遞增的正整數(shù)序列和一個正整數(shù) M,求序列中的兩個不同位置的數(shù)?a?和 b,使得它們的和恰好為 M,輸出所有滿足條件的方案。
本題的一個最直觀的想法是,使用二重循環(huán)枚舉序列中的整數(shù) a?和 b,判斷它們的和是否為 M。時間復雜度為 O(n2)。
two pointers?將利用有序序列的枚舉特性來有效降低復雜度。它針對本題的算法如下:
令下標 i?的初值為0,下標 j?的初值為?n-1,即令 i、j?分別指向序列的第一個元素和最后一個元素,接下來根據(jù) a[i]+a[j]?與 M?的大小來進行下面三種選擇,使 i?不斷向右移動、使 j?不斷向左移動,直到 i≥j?成立
-
- 若 a[i]+a[j]==M ,說明找到了其中一種方案,令 i=i+1、j=j-1。
- 若 a[i]+a[j]>M,令 j=j-1。
- 若 a[i]+a[j]<M,令 i=i+1。
反復執(zhí)行上面三個判斷,直到 i≥j?成立,時間復雜度為O(n),代碼如下:
1 while(i < j) { 2 if(a[i]+a[j] == M) { 3 printf("%d %d\n", i, j); 4 i++; j--; 5 } else if(a[i]+a[j] < M) { 6 i++; 7 } else { 8 j--; 9 } 10 }?
?
再來看序列合并問題。假設有兩個遞增序列 A?與 B,要求將它們合并為一個遞增序列 C。
同樣的,可以設置兩個下標?i?和? j ,初值均為0,表示分別指向序列 A?的第一個元素和序列 B?的第一個元素,然后根據(jù) A[i]?與 B[j]?的大小來決定哪一個放入序列 C。
-
- 若 A[i]≤B[j],把 A[i]?加入序列 C?中,并讓 i?加1
- 若 A[i]>B[j],把 B[j]?加入序列 C?中,并讓 j?加1
上面的分支操作直到 i、j?中的一個到達序列末端為止,然后將另一個序列的所有元素依次加入序列 C?中,代碼如下:
1 int merge(int A[], int B[], int C[], int n, int m) { 2 int i=0, j=0, index=0; // i指向A,j指向B,index指向C 3 while(i<n && j<m) { 4 if(A[i] <= B[j]) { // 若 A[i]≤B[j] 5 C[index++] = A[i++]; 6 } else { // 若 A[i]>B[j] 7 C[index++] = B[j++]; 8 } 9 } 10 while(i<n) C[index++] = A[i++]; // 若 A 有剩余 11 while(j<m) C[index++] = B[j++]; // 若 B 有剩余 12 return index; // 返回 C 長度 13 }?
?
?
?
廣義上的?two pointers?是利用問題本身與序列的特性,使用兩個下標 i、j?對序列進行掃描(可以同向掃描,也可以反向掃描),以較低的復雜度(一般為 O(n) )解決問題。?
?
?
歸并排序
歸并排序是一種基于“歸并”思想的排序方法,本節(jié)主要介紹其中最基本的 2-路歸并排序。2-路歸并排序的原理是,將序列兩兩分組,將序列歸并為?n/2?個組,組內(nèi)單獨排序;然后將這些組再兩兩歸并,生成?n/4?個組,組內(nèi)再單獨排序;以此類推,直到只剩下一個組為止。時間復雜度為 O(nlogn)。
1.?遞歸實現(xiàn)
只需反復將當前區(qū)間 [left,right]?分為兩半,對兩個子區(qū)間 [left,mid]?與 [mid+1, right]?分別遞歸進行歸并排序,然后將兩個已經(jīng)有序的子區(qū)間合并為有序序列即可。代碼如下:
1 const int maxn = 100; 2 // 將數(shù)組A的 [L1,R1] 與 [L2,R2] 合并為有序區(qū)間(此處 L2=R1+1 ) 3 void merge(int A[], int L1, int R1, int L2, int R2) { 4 int i=L1, j=L2; 5 int temp[maxn], index=0; // temp 臨時儲存合并序列 6 while(i<=R1 && j<=R2) { 7 if(A[i] <= A[j]) { // 若 A[i] ≤A[j] 8 temp[index++] = A[i++]; 9 } else { // 若 A[i] > A[j] 10 temp[index++] = A[j++]; 11 } 12 while(i <= R1) temp[index++] = A[i++]; 13 while(j <= R2) temp[index++] = A[j++]; 14 for(int i=0; i<index; ++i) { 15 A[L1+i] = temp[i]; // 將合并后的序列賦值回 A 16 } 17 } 18 } 19 // 歸并排序遞歸實現(xiàn) 20 // 只需反復將當前區(qū)間 [left,right] 分為兩半,對兩個子區(qū)間 [left,mid] 與 [mid+1, right] 21 // 分別遞歸進行歸并排序,然后將兩個已經(jīng)有序的子區(qū)間合并為有序序列即可。 22 void mergeSort(int A[], int left, int right) { 23 if(left < right) { // 當 left==right 時,只有一個元素,認定為有序 24 int mid = (left+right)/2; 25 mergeSort(A, left, mid); // 分為左區(qū)間和右區(qū)間 26 mergeSort(A, mid+1, right); 27 merge(A, left, mid, mid+1, right); // 將左區(qū)間和右區(qū)間合并 28 } 29 }?
?
?
?
2.非遞歸實現(xiàn)
非遞歸實現(xiàn)主要考慮到這樣一點:每次分組時組內(nèi)元素個數(shù)上限都是2的冪次。于是就可以想到這樣的思路:令步長 step?的初值為2,然后將數(shù)組中每 step?個元素作為一組,將其內(nèi)部進行排序;再令?step?乘以2,重復上面的操作,直到?step/2?超過元素個數(shù)?n 。代碼如下:
1 const int maxn = 100; 2 3 // 將數(shù)組A的 [L1,R1] 與 [L2,R2] 合并為有序區(qū)間(此處 L2=R1+1 ) 4 void merge(int A[], int L1, int R1, int L2, int R2) { 5 int i=L1, j=L2; 6 int temp[maxn], index=0; // temp 臨時儲存合并序列 7 while(i<=R1 && j<=R2) { 8 if(A[i] <= A[j]) { // 若 A[i] ≤A[j] 9 temp[index++] = A[i++]; 10 } else { // 若 A[i] > A[j] 11 temp[index++] = A[j++]; 12 } 13 while(i <= R1) temp[index++] = A[i++]; 14 while(j <= R2) temp[index++] = A[j++]; 15 for(int i=0; i<index; ++i) { 16 A[L1+i] = temp[i]; // 將合并后的序列賦值回 A 17 } 18 } 19 } 20 21 // 歸并排序非遞歸實現(xiàn) 22 // 令步長 step 的初值為2,然后將數(shù)組中每 step 個元素作為一組, 23 // 將其內(nèi)部進行排序;再令 step 乘以2,重復上面的操作,直到 step/2 超過元素個數(shù) n 。 24 void mergeSort(int A[]) { 25 // step 為組內(nèi)元素個數(shù) 26 for(int step=0; step/2 <= n; step *= 2) { 27 for(int i = 1; i <= n; i += step) { // 對每一組,數(shù)組下標從1開始 28 int mid = i + step/2 -1; // 左區(qū)間元素個數(shù)為 step/2 29 if(mid+1 <= n) { // 右區(qū)間存在元素 30 // 左區(qū)間為 [left,mid],右區(qū)間為 [mid+1, min(i+step-1,n) 31 merge(A, i, mid, mid+1, min(i+step-1, n)); 32 } 33 34 /* 35 // 也可以用 sort 代替 merge 函數(shù) 36 sort(A+i, A+min(i+step, n+1)); */ 37 } 38 } 39 }?
?
?快速排序?
快速排序的實現(xiàn)需要先解決這樣一個問題:對一個序列 A[1]、A[2]、... 、A[n],調(diào)整序列中元素的位置,使得 A[1] (原序列中的 A[1])的左側(cè)元素都不超過 A[1]、右側(cè)所有元素都大于 A[1]。
下面給出速度最快的做法,思想就是?two pointers:
1. 先將 A[1]?存至某個臨時變量 temp,并令兩個下標 left、right?分別指向序列首尾。
2.?只要 right?指向的元素 A[right]?大于 temp ,就將 right?不斷左移;當某個時候 A[right]?小于等于 temp?時,將元素 A[right]?挪到 left?指向的元素 A[left]?處。
3.?只要?left?指向的元素 A[right]?小于等于?temp ,就將 left 不斷右移;當某個時候 A[right]?大于?temp?時,將元素 A[left]?挪到 right指向的元素 A[right]?處。
4.?重復 2.3 ,直到 left?與?right?相遇,把 temp(也即原 A[1])放到相遇的地方。
1 // 對區(qū)間 [left,right]進行劃分 2 int Partition(int A[], int left, int right) { 3 int temp = A[left]; // 1. 4 while(left < right) { 5 while(left<right && A[right]>temp) right--; // 2. 6 A[left] = A[right]; 7 while(left<right && A[left]<=temp) left++; // 3. 8 A[right] = A[left]; 9 } 10 A[left] = temp; // 4. 11 return left; 12 }?
?
接下來就可以正式實現(xiàn)快速排序算法了。快速排序的思路是:
1.?調(diào)整序列中的元素,使當前序列的最左端的元素在調(diào)整后滿足左側(cè)所有元素均不超過該元素、右側(cè)所有元素均大于該元素
2.?對該元素的左側(cè)和右側(cè)分別進行 1?的調(diào)整,直到當前調(diào)整區(qū)間的長度不超過 1
快速排序的遞歸實現(xiàn)如下:
1 // 快速排序 2 void quickSort(int A[], int left, int right) { 3 if(left < right) { 4 int pos = Partition(A, left, right); // 1. 5 quickSort(A, left, pos); // 2. 6 quickSort(A, pos+1, right); 7 } 8 }?
快速排序算法當序列中元素的排列比較隨即時效率最高,但是當序列中元素接近有序時,會達到最壞時間復雜度 O(n2)。
其中一種解決辦法是隨機選擇主元,也就是對 A[left...right]?來說,不總是用 A[left]?作為主元,而是從?left...right 隨機選擇一個作為主元。
下面來看看如何生成隨機數(shù)。
- 需要添加 stdlib.h?與 time.h?頭文件。
- 函數(shù)開頭需加上??srand((unsigned)time(NULL));?,這個語句將生成隨機數(shù)的種子
- ??rand()?只能生成 [0,RAND_MAX]?范圍內(nèi)的整數(shù),RAND_MAX?在不同系統(tǒng)環(huán)境中不同,假設該系統(tǒng)為 32767
- ?如果想要輸出給定范圍 [a,b]?內(nèi)的隨機數(shù),需要使用??rand() % (b-a+1) + a??
- ?如果需生成更大的數(shù),例如 [a,b],b?大于 32767,可以使用??(int)(round(1.0*rand()/RAND_MAX*(b-a)+a))?
在此基礎上繼續(xù)討論快排的寫法。不妨生成一個范圍在 [left,right]?內(nèi)的隨機數(shù) p,然后以 A[p]?作為主元來進行劃分。具體做法是:將 A[p]?與 A[left]?交換,然后按原先 Partition?函數(shù)的寫法即可,代碼如下:
1 // 隨機選擇主元,然后進行劃分 2 int randPartition(int A[], int left, int right) { 3 // 生成 [left,right] 內(nèi)的隨機數(shù) p 4 int p = (int)(round(1.0*rand()/RAND_MAX*(right-left) +left)); 5 swap(A[p], A[left]); // 交換 A[p] 和 A[left] 6 7 // 以下跟 Partition 完全相同 8 return Partition(A, left, right); 9 }?
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/coderJiebao/p/Algorithmofnotes08.html
總結(jié)
以上是生活随笔為你收集整理的算法初步——two pointers的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: Python 基础知识整理-2
- 下一篇: VS2015配置内核WDK7600环境,