C++程序计算旋转次数以使给定数组按非递增顺序排序

问题描述

给定一个 n 元素数组，数组中的元素经过旋转后，使得数组成为以非递增顺序排列的。旋转次数指数组从原始位置到最终位置所需的移动次数。如 [7, 8, 9, 1, 2, 3, 4, 5, 6] 经过旋转后得到 [9, 8, 7, 6, 5, 4, 3, 2, 1]，旋转次数为3。

现在要求设计一个 C++ 程序计算旋转次数。

解决方案

方法一：暴力解法

最直观的思路是将数组旋转，从旋转0次开始，逐次旋转，直到得到非递增顺序排列的数组。所需旋转次数即为答案。

int bruteforce_rotate_count(int arr[], int n){
    for (int i = 0; i < n; i++) {
        int rotated_arr[n];
        for (int j = 0; j < n; j++) {
            int index = (j + i) % n;
            rotated_arr[j] = arr[index];
        }
        bool flag = true;
        for(int j = 1; j < n; j++){
            if(rotated_arr[j] > rotated_arr[j-1]){
                flag = false;
                break;
            }
        }
        if(flag) return i;
    }
    return n;
}

该方法的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n)$ ，对于较大的数组，时间复杂度太高。

方法二：二分法

考虑非递增顺序数组的特点：将非递增顺序数组的前面若干个元素移到数组后面，所得到的数组即为原数组旋转后的数组。因此，问题转化为在数组中寻找最小值的位置。寻找过程可用二分法实现，时间复杂度为 $O(log_2n)$ ，空间复杂度为 $O(1)$ 。

int binary_search_rotate_count(int arr[], int n){
    int left = 0, right = n - 1;
    while(left < right){
        int mid = (left + right) / 2;
        if(arr[mid] > arr[left]){
            right = mid;
        } else if(arr[mid] < arr[left]){
            left = mid + 1;
        } else{
            left++;
        }
    }
    return left;
}

测试结果

int main(){
    int arr1[] = {7, 8, 9, 1, 2, 3, 4, 5, 6};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    cout << binary_search_rotate_count(arr1, n1) << endl; //3
    cout << bruteforce_rotate_count(arr1, n1) << endl; //3

    int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    cout << binary_search_rotate_count(arr2, n2) << endl; //0
    cout << bruteforce_rotate_count(arr2, n2) << endl; //9

    int arr3[] = {2, 3, 4, 5, 6, 1};
    int n3 = sizeof(arr3) / sizeof(arr3[0]);
    cout << binary_search_rotate_count(arr3, n3) << endl; //5
    cout << bruteforce_rotate_count(arr3, n3) << endl; //5

    return 0;
}

程序输出：