當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

算法初步——two pointers

發(fā)布時間：2023/12/1 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了算法初步——two pointers 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

什么是 two?pointers　　

　　以一個例子引入：給定一個遞增的正整數(shù)序列和一個正整數(shù) M，求序列中的兩個不同位置的數(shù)?a?和 b，使得它們的和恰好為 M，輸出所有滿足條件的方案。

　　本題的一個最直觀的想法是，使用二重循環(huán)枚舉序列中的整數(shù) a?和 b，判斷它們的和是否為 M。時間復雜度為 O(n²)。

　　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(n²)。

　　其中一種解決辦法是隨機選擇主元，也就是對 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)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Python 基础知识整理－２
下一篇： VS2015配置内核WDK7600环境,