Leetcode-初级算法-数组循环右移_leetcode 数组循环移动k

本文首发于我的个人Blog阿西BUG，欢迎大家批评指正

题目

给定一个数组，将数组中的元素向右移动 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]
示例2
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明
- 尽可能想出更多解决方案，至少有三种不同的方法可以解决这个问题
- 要求使用空间复杂度为O(1)的原地算法

自己的思路

在数组元素个数 n 不为0的前提下，分3种情况
1.如果 k 和 n 相同，则数组不变
2.如果 k 小于 n ，则对数组进行 k 次循环，把最后一个元素移到第一个元素，其他依次后移
3.如果 k 大于 n ，则对数组进行 k-n 次循环，重复步骤2

耗时: 384ms

这个思路大概是最笨的方法，不得不承认，自己对于算法还是弱鸡。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty())
            return;

        if (nums.size() > k){
            for (int j = 0; j < k; j++){
                int temp = nums[nums.size() - 1];
                for (int i = nums.size() - 1; i > 0; i--){
                    nums[i] = nums[i - 1];
                }
                nums[0] = temp;
            }     
        }
        else if (nums.size() < k){
            rotate(nums, k-nums.size());
        } 

        for (int i = 0; i < nums.size(); i++){
            cout << nums[i];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

网上的优秀思路

这个思路是使用了C++标准库函数 reverse
假设输入数组的下标是0 ~ n-1，需要旋转的步数是k，那么按照下面的方法就可以完成旋转数组
（其中reverse表示用双指针交换的方法翻转数组）：
step 1. reverse原来的数组。
step 2. reverse 0~ k-1。
step 3. reverse k ~ n-1。
那么得到的新数组就是个旋转数组了。

举个例子来说是这样的：
元素组： 1 2 3 4 5 翻转步长：k=3
step 1 reverse原来的数组： 5 4 3 2 1
step 2 reverse 0~ k-1： 3 4 5 2 1
step 3 reverse k ~ n-1: 3 4 5 1 2
最后的【3 4 5 1 2】就是旋转数组的结果了，这种方法的时间复杂度是o（n），空间复杂度是o（1），是非常好的方法了
耗时: 12ms

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.begin(), nums.begin() + nums.size() - k);
        reverse(nums.begin() + nums.size() - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};
1
2
3
4
5
6
7
8
9