C++程序将数组左旋d个元素

前言

在做一些算法题或是项目时，可能会需要将一个数组进行旋转操作。比如将一个有序数组旋转k次后，使得旋转后的数组依然有序。其中一种旋转操作就是将数组左旋d个元素，也就是将数组的前d个元素移到数组的末尾。本篇文章将介绍C++语言中如何实现将一个数组左旋d个元素的操作。

方法一：暴力法

首先介绍一种暴力的方法，从第一个元素开始一个一个地将前d个元素移到数组的末尾，直到所有的元素都完成该操作。具体实现如下：

#include <iostream>

using namespace std;

void leftRotateByOne(int arr[], int n) {
    int temp = arr[0], i;
    for (i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1]; // 将当前元素赋值为下一个元素
    }
    arr[i] = temp; // 将第一个元素移到末尾
}

void leftRotate(int arr[], int d, int n) {
    for (int i = 0; i < d; i++) {
        leftRotateByOne(arr, n);
    }
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }, d = 2, n = 7;
    leftRotate(arr, d, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

代码中实现了两个函数：leftRotateByOne和leftRotate。其中，leftRotateByOne函数将数组的第一个元素移到末尾，leftRotate函数每次调用leftRotateByOne函数将数组前d个元素移到末尾，共执行d次操作，完成旋转操作。运行结果如下所示：

3 4 5 6 7 1 2

很明显，这种方法的时间复杂度为O(nd)，空间复杂度为O(1)。

方法二：利用STL

使用STL是一种更方便和高效的方法，使用rotate函数即可完成数组旋转操作。代码如下所示：

#include <iostream>
#include <algorithm> // 包含rotate函数

using namespace std;

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }, d = 2, n = 7;
    rotate(arr, arr + d, arr + n); // 将前d个元素旋转至数组末尾
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

代码中使用了<algorithm>头文件中的rotate函数，该函数接受三个参数：指向旋转操作的开始元素的迭代器、指向旋转操作的结束元素的下一个位置的迭代器，以及指向旋转操作的旋转点的迭代器。执行完rotate函数后，前d个元素就会被移到数组的末尾。运行结果如下所示：

3 4 5 6 7 1 2

利用STL的方法时间复杂度也为O(n)，但是实现更加方便快捷。

方法三：反转法

最后介绍一种反转的方法，通过多次翻转操作达到旋转数组的目的。首先将数组的前d个元素翻转，然后将后n-d个元素翻转，最后将整个数组翻转，操作即可完成。具体实现如下：

#include <iostream>

using namespacestd;

void reverse(int arr[], int start, int end) {
    while (start < end) {
        swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void leftRotate(int arr[], int d, int n) {
    if (d == 0 || d == n) // d等于0或n时不需旋转
        return;
    reverse(arr, 0, d - 1); // 将前d个元素翻转
    reverse(arr, d, n - 1); // 将后n-d个元素翻转
    reverse(arr, 0, n - 1); // 将整个数组翻转
}

int main() {
    int arr[] = { 1, 2, 3, 4, 5, 6, 7 }, d = 2, n = 7;
    leftRotate(arr, d, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

代码中实现了一个reverse函数，该函数将数组从start位置到end位置的元素翻转。leftRotate函数先将数组的前d个元素翻转，再将后n-d个元素翻转，最后将整个数组翻转，完成旋转操作。运行结果如下所示：