JavaScript プログラム: 配列がソートされているかどうかを確認し、回転します

#ソートされた配列は、すべての要素が昇順に配置された配列です。サイズ N の配列と、個別の整数を含む配列 (各整数は 1 回だけ出現することを意味します) が与えられます。配列がソートされ、時計回りに回転されているかどうかを確認する必要があります。ここで、配列がソートおよび回転される場合は「YES」を返す必要があり、それ以外の場合は「NO」を返す必要があります。

注 - ここでは並べ替えと回転について話しています。つまり、少なくとも 1 回の回転が必要であることを意味します。ソートされた配列をソートおよび回転された配列として扱うことはできません。

サイズ N

の配列が与えられたとします。 ＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

配列はソートされ、1 ビットずつ回転されます

リーリー

1 位置でソートされ、回転された配列は入力配列と一致するため、出力は「yes」になります。

＃＃＃入力＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

イラスト

指定された配列はソートされておらず、回転されていない配列です

リーリー

上記の並べ替えられた配列も回転された配列も入力配列と一致しないため、答えは「いいえ」です。

＃＃＃方法＃＃＃

ここでは 2 つの方法について説明します。次のセクションでそれらを見てみましょう -

方法 1: ピボット要素 (最小数) を見つけて配列がソートおよび回転されているかどうかを確認する

このメソッドの考え方は、最小数を見つけ、配列をソートして回転すると、最小数の前後の値がソートされた形になるはずであるということです。

＃＃＃例＃＃＃ リーリー

時間計算量 - O(N)、N は配列のサイズです。

スペースの複雑さ - 余分なスペースを使用していないため、O(1)。

方法 2: 隣接する反転を計算して配列がソートおよび回転されているかどうかを確認する

このメソッドの考え方は、配列を反復処理して、前の要素が現在の要素より小さいかどうかを確認するということです。ソートおよび回転された配列の場合、前の要素が現在の要素より大きい場合、カウントは 1 でなければなりません。それ以外の場合、配列はソートおよび回転されません。

＃＃＃例＃＃＃ リーリー

時間計算量 - O(N)、N は配列のサイズです。

スペースの複雑さ - 余分なスペースを使用していないため、O(1)。

＃＃＃結論は＃＃＃

このチュートリアルでは、配列がソートおよび回転されているかどうかを確認する方法について説明しました。ここでは 2 つの方法が示されています。1 つはピボット (最小の要素を意味します) を見つける方法で、もう 1 つは隣接する反転を計算することです。両方のメソッドの時間と空間の複雑さは同じです。つまり、それぞれ O(N) と O(1) です。

以上がJavaScript プログラム: 配列がソートされているかどうかを確認し、回転しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。