C++程序 打印给定数组的所有可能旋转

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]

方法:

按照下面的步骤解决问题:

  1. 通过逐步对数组进行左旋转,生成数组的所有可能旋转。
  2. 打印数组的所有可能旋转,直到遇到相同的数组旋转。

以下是上述方法的实现:

// 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)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例