หา Rotation Count ใน Rotated Sorted Array ใน C++

พิจารณา Array ที่เป็น Rotated Sorted Array ต้องการหาจำนวน Rotations ที่ต้องหมุนเพื่อให้ Array เรียงลำดับ (Rotation ขวาไปซ้าย)

ตัวอย่าง Array: {15, 17, 1, 2, 6, 11} ต้อง Rotate 2 ครั้ง จะได้ {1, 2, 6, 11, 15, 17} Output = 2

ตรรกะง่าย: จำนวน Rotation เท่ากับ Index ของ Minimum Element หา Minimum Element แล้ว Index คือคำตอบ

ตัวอย่างโค้ด C++

#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