美文网首页Leetcode
Leetcode.189.Rotate Array

Leetcode.189.Rotate Array

作者: Jimmy木 | 来源:发表于2019-11-19 11:42 被阅读0次

    题目

    给定一个数组和一个数字n, 进行n次操作, 每次都将数组的最后一个数字放到最前面.

    Input: [1,2,3,4,5,6,7], 3
    Output: [5,6,7,1,2,3,4]
    

    思路1

    将后n个数字提到前面即可.也可以不利用额外数组, 但内存都一样.

    void rotate(vector<int>& nums, int k) {
        int n = (int)nums.size();
        k = k % n;
        vector<int> first = vector<int>(nums.begin()+(n-k), nums.end());
        first.insert(first.end(), nums.begin(), nums.begin()+(n-k));
        nums = first;
    }
    

    思路2

    尽量利用更少的内存.

    void rotate(vector<int>& nums, int k)
    {
        int n = (int)nums.size();
        k = k % n;
        if (k > n-k) {
            // 前面移到后面
            vector<int> temp = vector<int>(nums.begin(), nums.begin()+(n-k));
            for (int i = 0; i < n;i++) {
                if (i < k) {
                    nums[i] = nums[n-k+i];
                } else {
                    nums[i] = temp[i-k];
                }
            }
        } else {
            // 后面移到前面
            vector<int> temp = vector<int>(nums.begin()+(n-k), nums.end());
            for (int i = 0; i < n;i++) {
                if (n-1-i >= k) {
                    nums[n-1-i] = nums[n-1-i-k];
                } else {
                    nums[n-1-i] = temp[n-1-i];
                }
            }
        }
    }
    

    总结

    对不同的情况分开分析, 尽量使用更少的内存.

    相关文章

      网友评论

        本文标题:Leetcode.189.Rotate Array

        本文链接:https://www.haomeiwen.com/subject/ynjwictx.html