算法题解——旋转数组

题目：

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路对比与分析

一、建立临时数组

下面是我自己的代码，通过开辟新数组来存放从后往前移的元素，剩下的移动到后边，然后再把新数组里的元素移动到前边。

做这道题我们特别要注意的一点就是k可能大于length，对于移动次数大于数组长度的情况，本质上就是移动k对length取模次。所以一开始就要将k赋值为k%len。

最后该算法使用了三次for循环，时间复杂度和空间复杂度均为O(n)。

class Solution {    
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k%len;
        int[] a = new int[k];
        if(k == 0)
            return;
        for(int i = 0;i<k;i++){
            a[i] = nums[len-k+i];   //赋值新数组
        }
        for(int i = len-k-1;i>=0;i--){
            nums[i+k] = nums[i];    //剩余元素移过去
        }
        for(int i = 0;i < k;i++){
            nums[i] = a[i];    //数组再赋值回去
        }
    }
}

同样的算法，下面是一段比较简单的代码

    public void rotate(int nums[], int k) {
        int length = nums.length;
        int temp[] = new int[length];
        //把原数组值放到一个临时数组中，
        for (int i = 0; i < length; i++) {
            temp[i] = nums[i];
        }
        //然后在把临时数组的值重新放到原数组，并且往右移动k位
        for (int i = 0; i < length; i++) {
            nums[(i + k) % length] = temp[i];
        }
    }

对比这两种方法，其实时间复杂度和空间复杂度都一样，但是细算时间和空间还是有差异的。我的代码是用时间换空间，虽然只建立k%len个大小的新数组，但却多了一次移动剩余元素的循环操作。而上述代码是直接将数组全移过来，从而放回时直接一个for就解决问题了。

二、环形算法

为了将空间复杂度降到最低，我最先想到的算法就是每次将最后一个元素提出，其余元素统统后移一位，然后把该元素放在第一个位置，总共移动k次。

class Solution {    
    public void rotate(int[] nums, int k) {
        int t = 0;
        int len = nums.length;
        k = k%len;
        for(int i = 0;i < k;i++){
            t = nums[len-1];
            for(int j = len-2;j >= 0;j--){
                nums[j+1] = nums[j];
            }
            nums[0] = t;
        }
    }
}

想法是好的，但是很明显，虽然空间复杂度仅为O(1)，但时间复杂度却达到了O()，这不仅令我无法接受，就连leecode的编译器都不认可（hhhhh，就是运行超时了wuwuwuwu。。。。。。）

那么我们来看看如何实现时间复杂度比较小，且空间复杂度还为O(1)的算法。

其实，我们看到，题目中所谓的旋转数组，归根结底就是把数组头尾相连当作环形，那么移动k位不就是每个元素都向前移动k位吗？我们直接将被覆盖元素提出来，不断地往该去的下一个位置走，直到走到最初的位置，不就用一次循环就可以解决问题吗？还需要注意的是，遍历过程中需要两个变量来保存数组元素，一个保存要替换变量，一个保存被替换变量。

  看起来这种方法确实可行，但在某些特殊情况下却存在实质性问题：

当数组长度是k的整数倍时（k!=1)，就会出现“反复横跳”的情况

例如：

 为了解决这一问题，我们需要引入一个变量count来统计遍历数目，如果回到了起点但count并不等于length，就从下一个位置开始继续遍历。

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        int count = 0;  //移动元素的个数
        int start = 0;  //遍历起始位置
        int temp1,temp2 = nums[0];//两个变量存放要移动的数组元素
        int i = 0;  //要操作的元素索引
        if(k == 0||len < 2)
            return;
        while(count != len){
            i = (i+k) % len;
            temp1 = nums[i];
            nums[i] = temp2;
            temp2 = temp1;
            count++;
            
            if(i == start){
                i = (i+1) % len;
                start = i;
                temp2 = nums[start];
            }
        }
    }
}

三、反转

其实看了原数组和旋转后的数组，我们不难发现，所谓的旋转数组就是先反转全部数组，在反转前k个，最后在反转剩余的

 代码如下

    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k %= length;
        reverse(nums, 0, length - 1);//先反转全部的元素
        reverse(nums, 0, k - 1);//在反转前k个元素
        reverse(nums, k, length - 1);//接着反转剩余的
    }

    //把数组中从[start，end]之间的元素两两交换,也就是反转
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

这种方法的时间复杂度和空间复杂度算是几种方法里最小的了，时间复杂度为O(n)，空间复杂度为O(1)。

本文部分内容转自：

作者：数据结构和算法
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2skh7/?discussion=x7EjsX
来源：力扣（LeetCode）