修練アルゴリズムの内功-two pointers

内容:

two pointers概要

a+b=M

シーケンス連結問題

集計ソート

クイックソート

1、two pointersの概要
two pointersはアルゴリズムプログラミングにおいて非常に重要な思想であり、プログラミング技術に傾き、私たちのプログラミングに非常に高いアルゴリズム効率を提供しています.
2、a+b=M
1つの例として、1つの増加した正の整数シーケンスと1つの正の整数Mを与え、シーケンス中の2つの異なる位置の数aとbを求め、彼らの和がちょうどMであり、すべての条件を満たすスキームを出力する.
最も直接的な方法:
二重ループ列挙シーケンスAおよびBを用いて、このようなaおよびbを見つけ、それらの和をMにする.

for(int i=0;i

このアプローチの時間的複雑さはO(n^2)レベルであり,我々のアルゴリズム要件には全く不十分である.
複雑度が高い理由:
既に決定されたA[i]に対して、A[i]+B[j]>Mが満たされている場合、A[i]+B[j+1]>Mも明らかに存在する.これは、jをいくら増やしても得られず、Mであるため、jが大量の無効な列挙を行うためである.
Two pointersを用いて複雑度をO(n)に低減する
アルゴリズムの手順:

令i=0,j=n-1;

A[i]+B[j]=Mであれば、条件を満たすとともに、右にi、左にi+、j--;

A[i]+B[j]の場合

A[i]+B[j]>Mの場合、どうしても移動iが2を成立させることができない場合、jを左に移動して2を成立させるしかない、すなわちj--;

i>=jまで2、3、4の判断を繰り返す.

コードは次のとおりです.

while(i

時間的複雑度はO(n)であり,第一のアプローチに対してアルゴリズム効率が大幅に最適化されることは明らかである.two pointersの思想はシーケンスの増加の性質を十分に利用し,複雑さを著しく低減することが分かった.
3、連結問題
2つの増分シーケンスAおよびBがある場合、それらは1つの増分シーケンスCに結合されることが要求される.
アルゴリズムプロセス:

は、i=0、j=0、index=0、iをシーケンスAの開始ビットとし、jをBの開始ビットとし、indexをCの開始ビットとする.

A[i]

A[i]>B[j]の場合、B[i]をシーケンスCに加え、jを1ビット右に移動させる、すなわちj++である.

A[i]==B[j]の場合、いずれかがシーケンスCに加えられ、下付き符号に1が付加される.

注意:上記のプロセスが完了したからといって、プログラムが終了したわけではなく、2つのシーケンスのうち1つのシーケンスが事前に完了した場合、すなわち、残りのシーケンスをCに追加し続ける必要がある.

コードは次のとおりです.

int merge(int A[],int B[],int C[],int n,int m){
     int i=0,j=0,index=0;
     while(i

4、集計ソート
並べ替えの考え方は簡単で、要約すると「二分並べ替え、秩序合併」である.1つのシーケンスを2つのサブシーケンスに分割し、この2つのサブシーケンスをそれぞれのソート作業を完了させた後、1つのシーケンスにマージします.同時に、このサブシーケンスも同様の操作を実行し、自分を2つの規模の小さいサブシーケンスに分割し、規模が1になるまでソートしてマージすることができます.
(1)、集計並べ替えの再帰的実現——2－道路集計並べ替え
ソート関数の実装:

int mergeSort(int arr[],int l,int r){//    ，                
    if(l

ソートが完了したシーケンス操作のマージ:

void merge(int arr[],int l,int mid,int r){
  int i=l,j=mid+1;
  int temp[maxn],index=0;
  while(i

(2)、非再帰的実現
2-ルーティング・ソートの非再帰的実装は、グループ化のたびにグループ内の要素の個数の上限が2のべき乗であることを主に考慮している.
そこで、このような考えがありました.

はステップ長stepの初期値を2にする.

は、次いで、配列内のstep個の要素をグループとして、その内部をソートする.

はさらにstepに2を乗算し、step/2が要素個数nを超えるまで上記の操作を繰り返す.

コードは次のとおりです.

void mergeSort(int arr[]){
    for(int step=2;step/2<=n;step*=2){
        for(int i=1;i<=n;i+=step){
           int mid=i+step/2-1;
           if(mid+1<=n){
              merge(arr,i,mid,min(i+step-1,n));
           }
        }
    }
}

もちろん、タイトルが集計ソートの各終了時のシーケンスのみを要求する場合は、merge関数の代わりにsort関数を使用することができます(時間制限が許容される限り).以下に示します.
sort(arr+i,arr+min(i+step,n+1)); 
5、クイックソート
高速ソートのアルゴリズム思想は、ヘッダ要素アドレスarr[0]を記述し、後の要素を1つずつ区分し、arr[0]より大きい要素を右に、arr[0]より小さい要素を左に置くことである.2つのサブシーケンスを形成し、サブシーケンスを上記の操作を繰り返し、サブシーケンスの規模が小さい、すなわち最後まで再帰すると、両側に直接秩序シーケンスが形成され、シーケンス全体が自然に秩序シーケンスである.
最初のステップは要素の分割を実現することです
 
コードは次のとおりです.
 

一時変数tempにarr[0]を保存させ、下付きlとrをシーケンスの左右両端、すなわちl=0、r=n-1を指す.

arr[r]>tempの場合、rはtempより大きくないまで右に移動し、arr[r]の値をarr[l]に割り当て、次のステップを実行する.

arr[l]

は、lとrが出会うまで23を繰り返し、最後にtempを出会いの位置に置けばよい.

void partition(int arr[],int l,int r){
   int temp=arr[l];
   while(ltemp)
            r--;             //    r
      arr[l]=arr[r];
      while(l

2つ目のステップは、迅速なソートを実現することです.

void quickSort(int arr[],int l,int r){
    if(r>l){
      int pos=Partition(arr,l,pos-1);
      quickSort(arr,l,pos-1);
      quickSort(arr,pos+1,r);
    }
}

高速ソートがさらに悪い場合の時間複雑度はO(n^2)であり,すなわちシーケンスが秩序に近い場合である.
まとめ:two pointersをうまく応用することはプログラミングの効率を高める重要な道である!!!
 
 
初心を忘れないで、ずっと!