C++程序 打印给定数组的所有可能旋转
给定一个大小为N的整数数组 arr[] ,任务是打印数组的所有可能的旋转。
示例:
输入: arr[] = {1, 2, 3, 4}
输出: {1, 2, 3, 4}, {4, 1, 2, 3}, {3, 4, 1, 2}, {2, 3, 4, 1}
解释:
初始 arr[] = {1, 2, 3, 4}
第一次旋转后 arr[] = {4, 1, 2, 3}
第二次旋转后 arr[] = {3, 4, 1, 2}
第三次旋转后 arr[] = {2, 3, 4, 1}
第四次旋转后, arr[] 返回其原始形式
输入: arr[] = [1]
输出: [1]
方法:
按照下面的步骤解决问题:
- 通过逐步对数组进行左旋转,生成数组的所有可能旋转。
- 打印数组的所有可能旋转,直到遇到相同的数组旋转。
以下是上述方法的实现:
// C++程序打印给定数组的所有可能旋转
#include <iostream>
using namespace std;
// 全局数组声明
int arr[10000];
// 反转s和e之间的数组
void reverse(int arr[],
int s, int e)
{
while(s < e)
{
int tem = arr[s];
arr[s] = arr[e];
arr[e] = tem;
s = s + 1;
e = e - 1;
}
}
// 生成数组的所有可能旋转
void fun(int arr[], int k)
{
int n = 4 - 1;
int v = n - k;
if (v >= 0)
{
reverse(arr, 0, v);
reverse(arr, v + 1, n);
reverse(arr, 0, n);
}
}
// 驱动程序
int main()
{
arr[0] = 1;
arr[1] = 2;
arr[2] = 3;
arr[3] = 4;
for(int i = 0; i < 4; i++)
{
fun(arr, i);
cout << ("[");
for(int j = 0; j < 4; j++)
{
cout << (arr[j]) << ", ";
}
cout << ("]");
}
}
// 本代码由Princi Singh贡献```
输出:
[1, 2, 3, 4] [4, 1, 2, 3] [2, 3, 4, 1] [3, 4, 1, 2]
时间复杂度: O(N2)
辅助空间: O(1)