右移数组K位（暴力法）代码问题：移位模块存在内存溢出

问题概述 #

在LeetCode解决数组右移K位问题时，以下暴力法C++代码存在内存溢出/数组越界问题，核心问题出在移位模块。本人已实现数组左移K位功能，确认该代码除移位逻辑外其余部分可正常运行。

示例用例 #

示例1 #

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释：

• 右移1步: [7,1,2,3,4,5,6]
• 右移2步: [6,7,1,2,3,4,5]
• 右移3步: [5,6,7,1,2,3,4]

示例2 #

输入: nums = [-1,-100,3,99], k = 2
输出: [3,99,-1,-100]
解释：

• 右移1步: [99,-1,-100,3]
• 右移2步: [3,99,-1,-100]

原问题代码 #

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = sizeof(nums)/sizeof(nums[0]);
        k = k%n;
        vector<int> temp;
        //storing the elements of the array till k places
        for(int i = 0; i < k; i++) {
            temp.push_back(nums[i]);
        }

        //shifting by k places
        for(int i = k; i<n;i++) {
            nums[i+k] = nums[i];
        }

        //putting the temp back to the place
        int j = 0;
        for(int i = n-k; i < n; i++) {
            nums[i] = nums[j];
            j++;
        }
    }
};

核心问题分析 #

1. vector长度计算错误：sizeof(nums)/sizeof(nums[0])仅适用于原生数组，对于vector，sizeof(nums)返回的是容器对象的内存大小，而非元素总大小。正确获取长度需用nums.size()。
2. 移位操作越界：原代码中nums[i+k] = nums[i]，当i取值接近n时，i+k会超出数组最大下标n-1，直接触发数组越界访问，导致内存溢出。
3. 临时数组存储逻辑错误：右移K位需要保存的是数组最后K个元素，而非前K个，原代码存储对象完全错误。
4. 临时数组回写错误：回写时原代码使用nums[j]，实际应写入temp[j]，否则等于覆盖原数组内容，无意义。

修正后的代码 #

优化暴力法（时间复杂度O(n)，空间复杂度O(k)） #

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n; // 处理k大于数组长度的情况
        
        // 保存数组最后k个元素
        vector<int> temp(nums.end() - k, nums.end());
        
        // 将前n-k个元素向右移动k位，从后往前遍历避免覆盖
        for (int i = n - k - 1; i >= 0; --i) {
            nums[i + k] = nums[i];
        }
        
        // 将临时数组的元素写回数组前k位
        for (int i = 0; i < k; ++i) {
            nums[i] = temp[i];
        }
    }
};

逐次右移暴力法（时间复杂度O(n*k)，空间复杂度O(1)） #

如果严格遵循逐次移位的暴力思路，可实现如下（效率较低，仅作参考）：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        
        for (int shift = 0; shift < k; ++shift) {
            int last_val = nums[n - 1];
            // 从后往前逐个元素右移
            for (int i = n - 1; i > 0; --i) {
                nums[i] = nums[i - 1];
            }
            nums[0] = last_val;
        }
    }
};

内容的提问来源于stack exchange，提问作者Shrish Bhargav