C++程序 检查在旋转数组后是否可以对其进行排序
给定一个大小为N的数组,任务是通过一个洗牌来确定是否可以只通过一个洗牌对数组进行排序。在一个洗牌中,我们可以将一些连续的元素从数组的末尾移动到数组的前面。
例如:
- A = {2, 3, 1, 2},我们可以将{1, 2}从数组的末尾移动到数组的前面以进行排序。
- A = {1, 2, 3, 2},由于我们无法在一个洗牌中对其进行排序,因此无法对数组进行排序。
例:
Input: arr[] = {1, 2, 3, 4}
Output: Possible
因为这个数组已经排序了,所以不需要洗牌。
Input: arr[] = {6, 8, 1, 2, 5}
Output: Possible
在原序列的前面按照相同的顺序放置最后三个元素,即{1, 2, 5, 6, 8}
方法:
- 检查数组是否已经排序。如果是,则返回true。
- 否则,开始遍历数组元素,直到当前元素小于下一个元素。存储arr[i] > arr[i+1]的索引。
- 从那一点开始遍历并检查从那个索引开始的元素是否按递增顺序排列。
- 如果上述两个条件都满足,则检查最后一个元素是否小于或等于给定数组的第一个元素。
- 如果上述三个条件都满足,则打印“可能”,否则如果上述3个条件中的任何一个失败,则打印“不可能”。
// 上述方法的 C++ 实现
#include
using namespace std;
// 检查是否有可能
bool isPossible(int a[], int n)
{
// 步骤 1
if (is_sorted(a, a + n)) {
cout << "Possible" << endl;
}
else {
// 找到 a[i] > a[i+1] 的地方
bool flag = true;
int i;
for (i = 0; i < n - 1; i++) {
if (a[i] > a[i + 1]) {
break;
}
}
// 断点 + 1
i++;
// 检查断点之后的序列是否进一步递增
for (int k = i; k < n - 1; k++) {
if (a[k] > a[k + 1]) {
flag = false;
break;
}
}
// 断点之后未递增
if (!flag)
return false;
else {
// 最后一个元素 <= 给定数组的第一个元素
if (a[n - 1] <= a[0])
return true;
else
return false;
}
}
}
// 主函数
int main()
{
int arr[] = { 3, 1, 2, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
if (isPossible(arr, n))
cout << "Possible";
else
cout << "Not Possible";
return 0;
}
输出:
Possible
时间复杂度:O(n)
空间复杂度:O(1)