この記事では、分割および征服アルゴリズムに基づいてJavaによって実装された線形時間選択操作について説明します。次のように、参照のために共有してください。
線形時間選択の問題: n要素と整数k、1≤k≤nが与えられた場合、これらのn要素の最小要素を見つける必要があります(ここで与えられた線形セットは無秩序です)。
ランダムに分割された線形選択
線形時間選択ランダム分割法は、ランダム化されたクイックソートアルゴリズムの設計を模倣できます。基本的なアイデアは、入力配列を再帰的に分割することです。クイックソートとは異なり、分割されたサブアレイの1つを再帰的に処理するだけです。
プログラムの説明:ランダム関数を使用してディビジョンベンチマークを生成し、配列a [p:r]を2つのサブアレイA [p:i]と[i+1:r]に分割します。これにより、[p:i]の各要素が[i+1:r]の各要素よりも大きくありません。次に、「j = i-p+1」は、a [p:i]の要素jの数を計算します。 k <= jの場合、[p:r]のk番目の最小要素はサブアレイa [p:i]にあり、k> jの場合、k番目の小さな要素はサブアレイa [i+1:r]にあります。注:サブアレイA [P:I]の要素はすべて発見されるk番目の小さな要素よりも小さいことが知られているため、[p:r]のk番目の小さな要素は[i+1:r]のk番目の小さな要素です。
たとえば、最悪の場合:最小の要素が常に見つかった場合、常に最大の要素で分割されます。これはO(n^2)の時間の複雑さです。ただし、平均時間の複雑さはnに直線的に関連しています。これはo(n)です
パッケージMath; Import Java.util.scanner; Import Java.util.random; public class randomSelect {public static void swap(int x、int y){int temp = x; x = y; y =温度; } public int random(int x、int y){random = new Random(); int num = random.nextint(y)%(y -x + 1) + x; numを返します。 } public intパーティション(int [] list、int low、int high){int tmp = list [low]; //配列の最初のものは中心軸ですwhile(low <high){while(low <high && list [high]> tmp){high--; } list [low] = list [high]; //中心軸よりも小さい記録はローエンドに移動しますが、low <high && list [low] <tmp){low ++; } list [high] = list [low]; //中心軸よりも大きい記録は、ハイエンドに移動されます}リスト[low] = tmp; //中心軸よりも大きいレコードは低く戻ります。 //中心軸の位置に戻る} public int randomizedPartition(int [] arrays、int left、int右){int i = random(左、右);スワップ(配列[i]、配列[左]);パーティションを返します(配列、左、右); } public int randomizedSelect(int [] arrays、int left、int right、int k){if(左==右){return arrays [左]; } int i = randomizedPartition(配列、左、右); int j = i-左 + 1; if(k <= j){return randomizedSelect(arrays、left、i、k); } else {return randomizedselect(arrays、i+1、右、kj); }} public static void main(string args []){system.out.println( "wulin.comテスト結果:"); int [] a = {7,5,3,4,8,6,9,1,2}; for(int i = 0; i <9; i ++){system.out.print(a [i]+""); } system.out.println(); randomSelect r = new RandomSelect(); system.out.println(「配列でクエリする最小要素は何ですか?」); @suppresswarnings( "Resource")スキャナーSC = new Scanner(System.in); int m = sc.nextint(); int n = R.RandomizedSelect(a、0,8、m); System.out.println( "The" the "the" the "in this array" + m + "最小の要素は" + n); }}実行結果:
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。