C++のRotatedSorted配列でRotationCountを検索します

回転してソートされた配列である配列があるとします。配列をソートするために必要な回転数を見つける必要があります。 （右から左への回転を検討します。）

配列が{15、17、1、2、6、11}のようであるとすると、配列を2回回転させて並べ替える必要があります。最終的な注文は{1、2、6、11、15、17}になります。ここでの出力は2です。

ロジックは単純です。気づいたら、回転数が最小要素のインデックスの値と同じであることがわかります。したがって、最小の要素を取得すると、そのインデックスが結果になります。

例

#include <iostream>
using namespace std;
int getMinIndex(int arr[], int n){
   int index = 0;
   for(int i = 1; i<n; i++){
      if(arr[i] < arr[index]){
         index = i;
      }
   }
   return index;
}
int countNumberOfRotations(int arr[], int n){
   return getMinIndex(arr, n);
}
int main() {
   int arr[] = {15, 17, 1, 2, 6, 11};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Number of required rotations: " << countNumberOfRotations(arr, n);
}

出力

Number of required rotations: 2