C++程序 将数组循环旋转一个位置

给定一个数组，将数组向右循环旋转一个位置。

例子：

输入：arr[] = {1, 2, 3, 4, 5}
输出：arr[] = {5, 1, 2, 3, 4}

下面是步骤。

1）将最后一个元素存储到变量x中。

2）将所有元素向前移动一个位置。

3）将数组的第一个元素替换为x。

// C++程序可循环旋转为一
//一个数组
# include <iostream>
using namespace std;

void rotate(int arr[], int n)
{
    int x = arr[n - 1], i;
    for (i = n - 1; i > 0; i--)
    arr[i] = arr[i - 1];
    arr[0] = x;
}

//驱动程序
int main()
{
    int arr[] = {1, 2, 3, 4, 5}, i;
    int n = sizeof(arr) /
            sizeof(arr[0]);

    cout << "给定的数组是
";
    for (i = 0; i < n; i++)
        cout << arr[i] << ' ';

    rotate(arr, n);

    cout << "
旋转后的数组是
";
    for (i = 0; i < n; i++)
        cout << arr[i] << ' ';

    return 0;
}

输出

给定的数组是 
1 2 3 4 5 

旋转后的数组是
5 1 2 3 4 

时间复杂度：O(n) 因为我们需要遍历所有元素

辅助空间：O(1)

上述问题也可以通过使用反转算法解决。

另一种方法：

我们可以使用两个指针，称为 i 和 j ，它们指向数组的 第一 和 最后一个 元素。 因为我们知道在循环旋转中，我们将把最后一个元素带到第一个位置，并向前移动其余元素，所以开始交换arr[i] 和arr[j] ，并固定j将i向j移动。 直到i不等于j时重复。

#include <iostream>
using namespace std;

void rotate(int arr[], int n)
{
    int i = 0, j = n-1; // i和j分别指向第一个和最后一个元素
    while(i != j){
    swap(arr[i], arr[j]);
    i++;
    }
}

//驱动程序
int main()
{
    int arr[] = {1, 2, 3, 4, 5}, i;
    int n = sizeof(arr) /
            sizeof(arr[0]);

    cout << "给定的数组是 \n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";

    rotate(arr, n);

    cout << "\n旋转后的数组是\n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}  

输出

给定的数组是 
1 2 3 4 5 
旋转后的数组是
5 1 2 3 4 

时间复杂度： O(n)

辅助空间： O(1)