C++程序 检查是否可以将数组旋转以使其增加或减少

C++程序 检查是否可以将数组旋转以使其增加或减少

给定一个由 N 个不同元素组成的数组 arr [] ,任务是通过向任何方向旋转数组来检查是否可能使数组增加或减少。

例子:

输入: arr [] = {4, 5, 6, 2, 3}

输出: 是的

数组可以旋转为 {2, 3, 4, 5, 6}

输入: arr [] = {1, 2, 4, 3, 5}

输出:

方法: 有四种可能性:

  • 如果数组 已经增加 ,则答案为 是的
  • 如果数组 已经减少 ,则答案为 是的
  • 如果数组可以使其增加,则此可能是因为给定的数组首先增加到最大元素,然后减少。
  • 如果数组可以使其减少,则此可能是因为给定的数组首先减少到最小元素,然后增加。

如果不能使数组增加或减少,则打印 No

下面是上面方法的实现:

//C++的实现方法
#include <bits/stdc++.h>
using namespace std;
 
//返回true,如果可以使数组递增或递减在旋转后的任何方向
bool isPossible(int a[], int n)
{
    //如果数组大小小于3
    if (n <= 2)
        return true;
 
    int flag = 0;
    //检查数组是否已经递减
    for (int i = 0; i < n - 2; i++) {
        if (!(a[i] > a[i + 1] and a[i + 1] > a[i + 2])) {
            flag = 1;
            break;
        }
    }
   
    //如果数组已经减少
    if (flag == 0)
        return true;
 
    flag = 0;
    //检查数组是否已经递增
    for (int i = 0; i < n - 2; i++) {
        if (!(a[i] < a[i + 1] and a[i + 1] < a[i + 2])) {
            flag = 1;
            break;
        }
    }
   
    //如果数组已经增加
    if (flag == 0)
        return true;
 
    //查找最小值和最大值的索引
    int val1 = INT_MAX, mini = -1, val2 = INT_MIN, maxi;
    for (int i = 0; i < n; i++) {
        if (a[i] < val1) {
            mini = i;
            val1 = a[i];
        }
        if (a[i] > val2) {
            maxi = i;
            val2 = a[i];
        }
    }
   
    flag = 1;
    //检查是否可以使数组递增
    for (int i = 0; i < maxi; i++) {
        if (a[i] > a[i + 1]) {
            flag = 0;
            break;
        }
    }
   
    //如果数组增加到最大索引并且最小元素在最大元素的右侧
    if (flag == 1 and maxi + 1 == mini) {
        flag = 1;
        //再次检查是否增加
        for (int i = mini; i < n - 1; i++) {
            if (a[i] > a[i + 1]) {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
            return true;
    }
   
    flag = 1;
    //检查是否可以使数组递减
    for (int i = 0; i < mini; i++) {
        if (a[i] < a[i + 1]) {
            flag = 0;
            break;
        }
    }
   
    //如果数组减小到最小索引并且最小元素在最大元素的左侧
    if (flag == 1 and maxi - 1 == mini) {
        flag = 1;
 
        //再次检查是否减少
        for (int i = maxi; i < n - 1; i++) {
            if (a[i] < a[i + 1]) {
                flag = 0;
                break;
            }
        }
        if (flag == 1)
            return true;
    }
   
    //如果不可能使数组递增或递减
    return false;
}
 
//主函数
int main()
{
    int a[] = { 4,5,6,2,3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    if (isPossible(a,n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}  

输出:

Yes

时间复杂度: O(n)

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例