在 C++ 中检查数组是否已排序和旋转

c++server side programmingprogramming

给定一个整数数组，任务是检查该数组是否已排序(升序)并在某个位置后旋转。

例如

输入 1:

N = [7, 8, 9, 4, 5, 6]

输出:

True

解释: 由于给定的数组是升序的，并且第 3 个位置之后的元素已旋转，因此在这种情况下我们将返回 True。

输入 2:

N = [1, 5, 7, 6, 2, 3]

输出:

False

解释: 由于给定的数组既不是按升序排列，也没有按某个特定位置旋转，因此输出为 False。

解决此问题的方法

我们有一个数组，其中元素按升序排列或未排序。如果数组必须排序和旋转，则至少会有一个元素，使得 N[i] > N[i+1]。

因此，对于每个 N[i]，我们将计算是否存在满足条件的任何元素，并相应地返回 True 或 False。

输入一个数组元素。
布尔函数 checkSortedandRotated(int *arr, int n) 将数组及其大小作为输入，如果数组已排序并旋转，则返回 true，否则返回 false。
遍历整个数组并计算 (arr[i] > arr[i+1]%n) 的元素数。如果计数为"1"，则返回 True，否则返回 False。
返回输出。

示例

#include <bits/stdc++.h>
using namespace std;
bool checkSortedandRotated(int * arr, int n) {
   int count = 0;
   for (int i = 0; i < n; i++) {
      if (arr[i] > arr[(i + 1) % n])
         count++;
   }
   return (count <= 1);
}
int main() {
   int arr[] = {5,6,7,1,2,3,4};
   int n = sizeof(arr) / sizeof(int);
   if (checkSortedandRotated(arr, n)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

运行上述代码将生成如下输出: