leetcode 189.旋转数组（C++）

113 阅读 0 评论 75 点赞

我是靠谱客的博主复杂日记本，这篇文章主要介绍leetcode 189.旋转数组（C++），现在分享给大家，希望可以做个参考。

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [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]

反转法

k可能比n大很多，所以需要对k %= n运算；

分组的时候，不是k的那个位置，而是要从后往前(n-k-1)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    void reverse(vector<int>& nums, int low, int high){
        while(low < high)
            swap(nums[low++], nums[high--]);
    }
public:
    void rotate(vector<int>& nums, int k){
        long n = nums.size();
        k %= n;
        if (k == 0)
            return;
        reverse(nums, 0, n-k-1);
        reverse(nums, n-k, n-1);
        reverse(nums, 0, n-1);
    }
};

直接插入法

用vector的插入操作，将后面的数字插到前面去，需要resize

复制代码

1
2
3
4
5
6
7
8
9
void rotate(vector<int>& nums, int k) {
        if(k % nums.size() == 0)
            return;
        k %= nums.size();
        size_t size = nums.size();
        
        nums.insert(nums.begin(),nums.begin() + nums.size() - k,nums.end()); //insert（pos,begin,end）      
        nums.resize(size);
    }