arrays - 並べ替えられたが回転された配列

Question

並べ替えられたが回転された配列が与えられた場合、どのようにピボットを見つけますか? インタビューでこんな質問をされました。回転配列とは

私はこれをインターネットで入手しましたが、まったく明確ではありません。

回転ソートされた配列では、A と B のいずれかのみがソートされることが保証されます。

ピボットは、左要素と右要素よりも小さい要素です。

Answer 1

ソートされ、回転された配列は次のようなものだと思います：

並べ替え:

2, 7, 32, 48, 55

回転:

 32, 48, 55, 2, 7

2ピボットです。ピボットの位置を見つける必要があります。

解決策は簡単です。ピボットは、並べ替えが終了して再開するポイントです。これは、「インターネットで見つけた」ものでもあります。

(配列が昇順でソートされていると仮定します。降順の場合は、に変更<し>ます)

for (i = 0; i<array.length; i++)
{
    if array[i+1] < array[i]
        return i + 1;
        break;
}

追加: すぐに思いついた分割統治ロジック。最初の要素が最後の要素よりも大きい限り、配列を分割し続けます。分割 (サブ) 配列の最初の要素が最後の要素よりも大きくない場合、最初の要素は元の配列のピボットです。

int left = 0;
int right = array.length - 1;
while (array[left] > array[right])
{
    int mid = left + (left + right) / 2;
    if(array[mid] > array[right])
    {
        left = mid + 1;
    }
    else
    {
        right = mid;
    }
}
return left;

ところで、インタビューでこの質問をされ、並べ替えられた回転配列が何であるかを知らなかった場合は、尋ねることができます。面接担当者があなたにそれを説明し、あなたが解決策を提供するなら、あなたは良いはずです. 個人的には、誰かが用語を知らなくても気にしません。彼らが考え、ロジックとコードを見つけることができる限り、それは問題ないはずです。