使用vector的erase函数实现数组右旋时遇到问题求排查

问题描述 #

给定整数数组nums，将数组向右旋转k步（k为非负整数）。

提交的代码 #

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k=k%n;
        for(int i=0;i<=k;i++){
            nums.push_back(nums[i]);
        }
        nums.erase(nums.begin(),nums.begin()+k+1);
    }
};

测试用例及错误结果 #

• 输入：[-1,-100,3,99]，k=2
• 实际输出：[99,-1,-100,3]
• 预期输出：[3,99,-1,-100]

错误原因分析 #

1. 逻辑方向完全错误：数组向右旋转k步的本质是将数组末尾的k个元素移动到数组开头，而非将前k个元素移到末尾。你的代码逻辑搞反了移动对象，导致结果不符合预期。
2. 循环条件错误：i<=k会让循环执行k+1次，多取了一个元素。比如k=2时，你取了前3个元素而非2个，进一步加剧了结果错误。

修正后的代码 #

按照你的push_back+erase思路，修正后的代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        // 将数组末尾的k个元素添加到数组尾部
        for (int i = n - k; i < n; ++i) {
            nums.push_back(nums[i]);
        }
        // 删除原数组的前n个元素，留下新增的k个元素+原数组前n-k个元素
        nums.erase(nums.begin(), nums.begin() + n);
    }
};

额外优化思路 #

如果追求更高效率，可以使用数组反转法（时间复杂度O(n)，空间复杂度O(1)）：

1. 反转整个数组；
2. 反转前k个元素；
3. 反转后n-k个元素。

代码示例：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

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