【力扣/牛客刷题】189. 轮转数组

xxxflower

发布于 2023-04-16 17:40:23

1390

发布于 2023-04-16 17:40:23

文章被收录于专栏：《数据结构》

力扣题目：轮转数组 ~~(需要看答案的uu可以直接跳到第三种解题思路，前两种是自己的思路，时间复杂度都太高。)~~

【1】分析思路一：首先我们可以创建一个临时变量temp，将数组中最后一个值放入temp中，然后依次将数组的值通过循环往后移动。

于是我们可以写出下列代码：

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

这样写代码是没有语法问题单，但是！这样写超过了题目所规定的时间复杂度。如下：

~~这是一件令人伤心的事情！T.T 5555~~ 我们来换一种思路：

然后：我们会得到以下代码：

class Solution {
    public void rotate(int[] nums, int k) {
        for(int i = 0;i < k ;i++){
            int[] arr1 = new int[nums.length];
            arr1[0] = nums[nums.length - 1];
            for(int j = 1;j < nums.length ;j++){
                arr1[j] = nums[j-1];
            }
            for(int m = 0;m < nums.length; m++){
                nums[m] = arr1[m];
            }
        }
    }
}

很好。然后…

叒不对，我真是，555太难过了。我们再换种思路（官方提供）：

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reserve(nums,0,n-1);
        reserve(nums,0,k-1);
        reserve(nums,k,n-1);
    }
    public void reserve(int[] nums,int start,int end){
        for(int i = start,j = end;i < j;i++,j--){
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }
}