循环数组C++向右移动

基础概念

循环数组是一种特殊的数组结构，其中元素的末尾会连接到数组的开头，形成一个环状结构。在这种结构中，对数组的访问和操作可以像在一个环形链表上一样进行。

类型

循环数组主要可以分为两种类型：

固定大小的循环数组：这种数组的大小是固定的，一旦创建就不能改变。
动态大小的循环数组：这种数组的大小可以根据需要进行动态调整。

应用场景

循环数组常用于以下场景：

缓冲区：在处理实时数据流时，循环数组可以作为缓冲区，存储最新的数据。
游戏开发：在游戏开发中，循环数组可以用于实现角色的移动、碰撞检测等。
时间窗口计算：在数据分析中，循环数组可以用于计算滑动时间窗口内的统计数据。

C++向右移动实现

假设我们有一个固定大小的数组 arr，长度为 n，我们需要将其向右移动 k 个位置。以下是一个简单的 C++ 实现：

#include <iostream>
#include <vector>

void rotateRight(std::vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n; // 处理 k 大于数组长度的情况
    if (k == 0) return; // 如果 k 为 0，不需要移动

    std::vector<int> temp(n);
    for (int i = 0; i < n; ++i) {
        temp[(i + k) % n] = arr[i];
    }
    arr = temp;
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int k = 2;
    rotateRight(arr, k);

    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

参考链接

C++标准库 - vector

遇到的问题及解决方法

问题：数组越界

原因：在处理数组时，如果索引计算错误，可能会导致数组越界。

解决方法：确保所有索引计算都在合法范围内。例如，在上面的代码中，我们使用了 (i + k) % n 来确保索引不会超出数组的范围。

问题：性能问题

原因：如果数组非常大，直接复制整个数组可能会导致性能问题。

解决方法：可以使用原地旋转算法，例如“三次翻转法”来减少空间复杂度。

void reverse(std::vector<int>& arr, int start, int end) {
    while (start < end) {
        std::swap(arr[start], arr[end]);
        start++;
        end--;
    }
}

void rotateRightInPlace(std::vector<int>& arr, int k) {
    int n = arr.size();
    k = k % n;
    if (k == 0) return;

    reverse(arr, 0, n - 1);
    reverse(arr, 0, k - 1);
    reverse(arr, k, n - 1);
}