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

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

方法

  • 找到数组中的最小元素。
  • 如果数组已排序并旋转,则将最小元素之前的所有元素都是递增顺序,最小元素之后的所有元素也是递增顺序。
  • 检查最小元素之前的所有元素是否是递增顺序。
  • 检查最小元素之后的所有元素是否是递增顺序。
  • 检查数组的最后一个元素是否小于起始元素。
  • 如果上述三个条件均满足,则输出 YES , 否则输出 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 clockwise
void 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 code
int 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:

  1. 遍历数组从第二个元素到最后一个元素,并检查当前元素是否小于前一个元素。如果是,则数组旋转了。
  2. 如果数组旋转了,则找到数组中最小元素的索引。这可以通过再次遍历数组并跟踪最小元素及其索引来完成。
  3. 非降序比较元素,从最小元素开始循环比较到前一个元素。如果所有元素都是非降序的,则数组已排序和旋转。
#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;
}  

输出

YES
YES
NO
NO

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

辅助空间:O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程