C++程序 判断数组是否排序且旋转

给定一个包含N个不同整数的数组。编写一个程序，检查这个数组是否按逆时针排序并旋转了。已排序的数组不被视为被排序和旋转，即至少应该进行一次旋转。

示例 ：

输入 ：arr[] = {3, 4, 5, 1, 2}
输出 ：YES
上述数组已经排序并旋转。
排序后的数组：{1, 2, 3, 4, 5}。
将这个排序好的数组顺时针旋转3个位置，我们得到：{3, 4, 5, 1, 2}

输入 ：arr[] = {7, 9, 11, 12, 5}
输出 ：YES

输入 ：arr[] = {1, 2, 3}
输出 ：NO

输入 ：arr[] = {3, 4, 6, 1, 2, 5}
输出 ：NO

方法 ：

下面是上述思路的实现：

// CPP program to check if an array is// sorted and rotated clockwise#include <climits>#include <iostream> using namespace std; // Function to check if an array is// sorted and rotated clockwisevoid checkIfSortRotated(int arr[], int n){    int minEle = INT_MAX;    int maxEle = INT_MIN;     int minIndex = -1;     // Find the minimum element    // and it's index    for (int i = 0; i < n; i++) {        if (arr[i] < minEle) {            minEle = arr[i];            minIndex = i;        }    }     int flag1 = 1;     // Check if all elements before minIndex    // are in increasing order    for (int i = 1; i < minIndex; i++) {        if (arr[i] < arr[i - 1]) {            flag1 = 0;            break;        }    }     int flag2 = 1;     // Check if all elements after minIndex    // are in increasing order    for (int i = minIndex + 1; i < n; i++) {        if (arr[i] < arr[i - 1]) {            flag2 = 0;            break;        }    }     // Check if last element of the array    // is smaller than the element just    // starting element of the array    // for arrays like [3,4,6,1,2,5] - not circular array    if (flag1 && flag2 &&(arr[n - 1] < arr[0]))        cout << "YES";    else        cout << "NO";} // Driver codeint main(){    int arr[] = { 3, 4, 5, 1, 2 };    int n = sizeof(arr) / sizeof(arr[0]);     // Function Call    checkIfSortRotated(arr, n);    return 0;}  

输出

YES

时间复杂度: O(N)，其中N表示给定数组的大小。

辅助空间: O(1)，不需要额外的空间，因此是一个常数。

Approach Name: 线性搜索

Steps:

遍历数组从第二个元素到最后一个元素，并检查当前元素是否小于前一个元素。如果是，则数组旋转了。如果数组旋转了，则找到数组中最小元素的索引。这可以通过再次遍历数组并跟踪最小元素及其索引来完成。非降序比较元素，从最小元素开始循环比较到前一个元素。如果所有元素都是非降序的，则数组已排序和旋转。

#include <iostream>using namespace std; bool isSortedAndRotated(int arr[], int n) {    bool rotated = false;    int min_index = 0;    int min_element = arr[0];    for (int i = 1; i < n; i++) {        if (arr[i] < arr[i - 1]) {            rotated = true;        }        if (arr[i] < min_element) {            min_index = i;            min_element = arr[i];        }    }    if (!rotated) {        return false;    }    for (int i = 1; i < n; i++) {        int index = (min_index + i) % n;        int prev_index = (min_index + i - 1) % n;        if (arr[index] < arr[prev_index]) {            return false;        }    }    return true;} int main() {    int arr1[] = { 3, 4, 5, 1, 2 };    int arr2[] = { 7, 9, 11, 12, 5 };    int arr3[] = { 1, 2, 3 };    int arr4[] = { 3, 4, 6, 1, 2, 5 };    int n1 = sizeof(arr1) / sizeof(arr1[0]);    int n2 = sizeof(arr2) / sizeof(arr2[0]);    int n3 = sizeof(arr3) / sizeof(arr3[0]);    int n4 = sizeof(arr4) / sizeof(arr4[0]);    if (isSortedAndRotated(arr1, n1)) {        cout << "YES\n";    } else {        cout << "NO\n";    }    if (isSortedAndRotated(arr2, n2)) {        cout << "YES\n";    } else {        cout << "NO\n";    }    if (isSortedAndRotated(arr3, n3)) {        cout << "YES\n";    } else {        cout << "NO\n";    }    if (isSortedAndRotated(arr4, n4)) {        cout << "YES\n";    } else {        cout << "NO\n";    }    return 0;}  

输出

YESYESNONO

时间复杂度：O(n)，其中n是输入数组的大小。

辅助空间：O(1)