leetcode 189. 轮转数组

╰半夏微凉° 2023-09-26 09:43 53阅读 0赞

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 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\]

提示：  
1 <= nums.length <= 105  
\-231 <= nums\[i\] <= 231\-1  
0 <= k <= 105

思路：  
可以将后面的元素放到前面，也可以把前面的元素放在末尾，2种的情况都差不多。  
我将前面的元素放在后面了，因为用的也是vector，有库函数可以使用，可以直接加到vector的尾部，然后再用erase删除前面的元素就可以了。

用erase删除元素时，可以直接删除一个区间，也可以用循环删除。但是用循环定义一个迭代器，一个一个删的话会超时。

//nums.erase(nums.begin(),nums.begin()+m);
            int i=0;
            for(vector<int>::iterator it=nums.begin();i<m;++i)
                nums.erase(it);

超时：

![在这里插入图片描述][133f7da285f8467aa0ee0be28a1b4a3a.png]

还有一个要注意的就是：  
erase函数的返回的是指向被删除元素的下一个元素的迭代器，所以执行erase（）后要把迭代器减1，指向前面一个，执行循环+1的时候就可以恢复到正常位置了。所以我就没有在循环中写迭代器加一的操作，反正删除掉一个就到下一个了，后面也都是要被删除的。

正确代码：

class Solution {
        
    public:
        void rotate(vector<int>& nums, int k) {
        
            int n=nums.size();
            if(k>n)   //这里特别要注意，如果需要轮换的次数超过数组的长度，其实是又回到原来的数组
                k%=n;
            int m=n-k;
            for(int i=0;i<m;++i)
                nums.push_back(nums[i]);
            nums.erase(nums.begin(),nums.begin()+m);
        }
    };

[133f7da285f8467aa0ee0be28a1b4a3a.png]: https://img-blog.csdnimg.cn/133f7da285f8467aa0ee0be28a1b4a3a.png