アルゴリズムのインタビューでは、インタビュアーは常にリンクされたリスト、ソート、バイナリツリー、バイナリ検索に関する記事を作成するのが好きで、ほとんどの人はプロの本をフォローしてそれらを記憶することができます。インタビュアーは、優れたメモリスキルを備えたプログラマーを募集したくありませんが、それを学んで適用することはできません。したがって、問題を数学的にモデル化および分析し、合理的なアルゴリズムまたはデータ構造を使用して問題を解決することを学ぶことが非常に重要です。
インタビューの質問：回転配列の最小数を印刷する
タイトル：アレイの最初のいくつかの要素を配列の最後に移動します。これを配列の回転と呼びます。増分分類された配列の回転を入力し、回転配列の最小要素を出力します。たとえば、配列{3、4、5、1、2}は配列{1、2、3、4、5}の回転であり、配列の最小値は1です。
この要件を達成するには、配列を通過し、最小値を見つけ、ループを直接終了するだけです。コードの実装は次のとおりです。
public class test08 {public static int getthemin（int nums []）{if（nums == null || nums.length == 0）{throw new runtimeexception（ "input error！"）; } int result = nums [0]; for（int i = 0; i <nums.length -1; i ++）{if（nums [i + 1] <nums [i]）{result = nums [i + 1];壊す; }} return result; } public static void main（string [] args）{//典型的な入力、単調な上昇配列の回転int [] array1 = {3、4、5、1、2}; System.out.println（getthemin（array1））; //重複した数字があり、最小数は最小の数字ですint [] array2 = {3、4、5、1、1、2}; system.out.println（getthemin（array2））; //重複した数値がありますが、重複した数値は最初と最後の数字ではありませんint [] array3 = {3、4、5、1、2、2}; System.out.println（getthemin（array3））; //重複した数字があり、重複した数値はたまたま最初と最後の数字であり、int [] array4 = {1、0、1、1、1}; System.out.println（getthemin（array4））; //単調な配列を昇順にし、0の要素を回転させます。つまり、単調な昇順配列自体をint [] array5 = {1、2、3、4、5}; system.out.println（getthemin（array5））; // array int [] array6 = {2}には1つの数値しかありません。 system.out.println（getthemin（array6））; //配列内の数値は同じint [] array7 = {1、1、1、1、1、1、1}です。 system.out.println（getthemin（array7））; }}結果の印刷には何の問題もありません。ただし、この方法は明らかに最良ではありません。対処するためのより良い方法を見つける方法があるかどうかを見てみましょう。
整然と、まだ検索する必要がありますか？
これらの2つのキーワードを見つけると、必然的にバイナリ検索方法について考えますが、多くの友人は、回転後に配列が真に注文された配列ではなくなったことを間違いなく尋ねますが、2つの増分配列の組み合わせのようなものです。私たちはこのように考えることができます。
2つの添え字を低く、高く設定し、Mid =（low + high）/2を設定でき、アレイの中央にある要素配列[MID]を自然に見つけることができます。中央の要素が正面の増分配列にある場合、それは低添字の対応する要素以上に等しくなければなりません。この時点で、配列内の最小の要素は要素の背後にある必要があります。低いサブスクリプトを中間要素に向けることができます。これにより、検索の範囲を狭めることができます。
同様に、中間要素が後続の増分サブアレイにある場合、それは高い添字に対応する要素よりも等しく、または等しくなければなりません。この時点で、配列内の最小の要素は中間要素の前にある必要があります。高いサブスクリプトをサブスクリプトの中央値に更新することができます。これにより、検索の範囲も狭くなる可能性があります。移動後の高い添え字に対応する要素は、まだその後の増分サブアレイにあります。
低くしようと高くするか、高くしているかにかかわらず、検索範囲は元の半分に削減されます。次に、更新されたサブスクリプトを使用して、新しいラウンドの検索を繰り返します。最後の2つのサブスクリプトが隣接するまで、つまりループエンド条件です。
私は多くのことを言ってきましたが、私は混乱しているようです。質問の入力を使用して、アルゴリズムをシミュレートして検証することもできます。
コードを使用してJavaにこのアイデアを実装する方法を見てみましょう。
public class test08 {public static int getthemin（int nums []）{if（nums == null || nums.length == 0）{throw new runtimeexception（ "input error！"）; } //要素が1つしかない場合、（nums.length == 1）if（nums.length == 1）を直接返す[0]; int result = nums [0]; int low = 0、high = nums.length -1; int mid; //低サブスクリプトに対応する値が左の増分サブアレイにあることを確認し、高に対応する値は右側の増分サブアレイにあります（nums [low]> = nums [high]）{//ループ条件の終了を確保する（高== 1）{return nums [high]; } //中央の位置を取ります=（low + high） / 2; //中央の要素が左に増分されていることを示します（nums [MID]> = nums [low]）{low = mid; } else {high = mid; }} return result; } public static void main（string [] args）{//典型的な入力、単調な上昇配列の回転int [] array1 = {3、4、5、1、2}; System.out.println（getthemin（array1））; //重複した数字があり、数字を繰り返すだけの最小数はint [] array2 = {3、4、5、1、1、2}; system.out.println（getthemin（array2））; //重複した数値がありますが、重複した数値は最初と最後の数字ではありませんint [] array3 = {3、4、5、1、2、2}; System.out.println（getthemin（array3））; //重複した数字があり、重複した数値はまさに最初と最後の数字ですint [] array4 = {1、0、1、1、1}; System.out.println（getthemin（array4））; //単調な昇順配列、0の要素を回転させます。つまり、単調な上昇配列自体はint [] array5 = {1、2、3、4、5}; system.out.println（getthemin（array5））; // array int [] array6 = {2}には1つの数値しかありません。 system.out.println（getthemin（array6））; //配列内の数値は同じint [] array7 = {1、1、1、1、1、1、1、1}です。 system.out.println（getthemin（array7））; //特別な私は、int [] array8 = {1、0、1、1、1}を移動する方法がわかりません。 System.out.println（getthemin（array8））; }}回転配列では、刻まれた配列のいくつかの数値が配列の後ろに移動されるため、最初の数値は常に最後の数値以上であるため、0個の要素が移動される別の特別なケース、つまりアレイ自体が独自の回転アレイでもあると述べました。この状況自体が順序付けられるため、最初の要素を返すだけです。そのため、結果を最初にnums [0]に割り当てます。
上記のコードは完璧ですか？テストケースを通じて要件を満たしていませんでした。 Array8入力を詳細に見てみましょう。最初にコンピューターの操作を分析しましょう。
しかし、一目で最小値は1ではなく0であることがわかります。したがって、配列[低]、配列[中]、および配列[高]が等しい場合、プログラムは移動方法を知りません。現在の動き方法によれば、アレイ[MID]はデフォルトで左側に増加します。これは明らかに無責任です。
コードを修正しましょう：
public class test08 {public static int getthemin（int nums []）{if（nums == null || nums.length == 0）{throw new runtimeexception（ "input error！"）; } //要素が1つしかない場合、（nums.length == 1）if（nums.length == 1）を直接返す[0]; int result = nums [0]; int low = 0、high = nums.length -1; int mid = low; //低サブスクリプトに対応する値が左の増分サブアレイにあることを確認し、高に対応する値は右側の増分サブアレイにあります（nums [low]> = nums [high]）{//ループ条件の終了を確保する（高== 1）{return nums [high]; } //中央の位置を取ります=（low + high） / 2; // 3つの値が等しい特別な場合、if（nums [mid] == nums [low] && nums [mid] == nums [high]）{return midinorde（nums、low、high）; } //中央の要素が左に増分されていることを示します（nums [Mid]> = nums [low]）{low = mid; } else {high = mid; }} return result; } / *** arrayの最小値を見つけます** @param nums array* @param start array start position* @param end array end position* @return見つかった最小数* / public static int midinorde（int [] nums、int start、int result = nums [start]; for（int i = start+1; i <= end; i ++）{if（result> nums [i]）result = nums [i]; } return result; } public static void main（string [] args）{//典型的な入力、単調な上昇配列の回転int [] array1 = {3、4、5、1、2}; System.out.println（getthemin（array1））; //重複した数値と、たまたま最も一般的な数値である最小数があります。 system.out.println（getthemin（array2））; //重複した数値がありますが、重複した数値は最初と最後の数字ではありませんint [] array3 = {3、4、5、1、2、2}; System.out.println（getthemin（array3））; //重複した数字があり、重複した数値はまさに最初と最後の数字ですint [] array4 = {1、0、1、1、1}; System.out.println（getthemin（array4））; //単調な昇順配列、0の要素を回転させます。つまり、単調な上昇配列自体はint [] array5 = {1、2、3、4、5}; system.out.println（getthemin（array5））; // array int [] array6 = {2}には1つの数値しかありません。 system.out.println（getthemin（array6））; //配列内のすべての数値は同じint [] array7 = {1、1、1、1、1、1、1}です。 system.out.println（getthemin（array7））; //特別な私は、int [] array8 = {1、0、1、1、1}を移動する方法がわかりません。 System.out.println（getthemin（array8））; }}次に、完全なテストケースとテストパスを使用して配置します。
要約します
実際、この質問には調べるべき多くのポイントがありますが、実際にはバイナリ検索の柔軟なアプリケーションを調べることです。多くの友人は、バイナリ検索のアイデアを学ぶことなく、バイナリ検索を整然と覚えておく必要があります。
インタビュー中に、多くの友人がAndroidの元のエコシステムが基本的に共通のアルゴリズムをカプセル化し、インタビューでこれらの効果のないアルゴリズムに抗議したという声明を発表しました。これは実際には非常に愚かです。 Roteアルゴリズムを実装しようとはしていませんが、その中で巧妙なアイデアを学ぶことを目指しています。常に自分の思考能力を改善することによってのみ、より良いキャリア開発を得るのに役立ちます。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。