数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查C++中数组是否已排序并旋转
给定一个整数数组，任务是检查数组是否已排序（升序）并在某个位置之后旋转。
例如
输入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;
}运行上述代码将生成以下输出：
输出
True
由于给定的数组[5, 6, 7, 1, 2, 3, 4]已排序并从第3个位置旋转，因此在这种情况下输出为'True'。
更新于： 2021年2月23日
2K+ 浏览量
广告