leetcode13 Rotate Array

刺骨的言语ヽ痛彻心扉 2021-12-14 04:45 218阅读 0赞

Given an array, rotate the array to the right by k steps, where k is non-negative.
    
    Example 1:
    
    Input: [1,2,3,4,5,6,7] and k = 3
    Output: [5,6,7,1,2,3,4]
    Explanation:
    rotate 1 steps to the right: [7,1,2,3,4,5,6]
    rotate 2 steps to the right: [6,7,1,2,3,4,5]
    rotate 3 steps to the right: [5,6,7,1,2,3,4]
    Example 2:
    
    Input: [-1,-100,3,99] and k = 2
    Output: [3,99,-1,-100]
    Explanation: 
    rotate 1 steps to the right: [99,-1,-100,3]
    rotate 2 steps to the right: [3,99,-1,-100]
    Note:
    
    Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
    Could you do it in-place with O(1) extra space?

这道题真的搞死我了，最后才清楚了题的意思，下面是我的实现思路，被leetcode接受后，我又去阅读了一下discuss里面的解题思路和别的算法，学学大神的思路和解题技巧。  
题目意思大概就是给你一个数组，和一个非负数k，然后将这个数组按照k步，从原数组的最后一个元素挪到第一个元素，每次都是一个新数组，一直挪到k为0才停止。一定要注意我的解释，比如我给你数组是\[1,2\]，指定的k是5，那么你就需要循环挪5次，最后结果应该是

k=1 [2,1] k=2 [1,2] k=3 [2,1] k=4 [1,2] k=5 [2,1]//最终的答案应该是[2,1]。

空间复杂度最好是O(1)，至少有三种不同的解法，啧啧啧，真的是有吧 比如我想过用栈或者队列都可以，但是最后的结果都需要赋值给元数组。

这道题开始我用栈最后思路不对，想的复杂，然后就换了数组，对于数组之中有一个特别注意的地方，每次挪完生成的新数组，我们需要把值赋给那个数组，而不是直接指向同一地址，我做的时候就犯了个错，  
`nums = a`；这样你在循环的时候，如果改了a的值，那么nums的值也会同步改动，因为他们指向的是同一地址。

下面是我的思路：

1.  当k为0的时候，什么也不做；
2.  当k不等于0的时候，那么我就需要将数组最后一个元素移动多少次，但是数组的长度还是原来长度，只是数组的结构发生了变化。
3.  所以新数组的第一个元素永远是原来数组的最后一个元素，然后依次把原来数组的第一个到第n-1个元素赋值给新元素的第2个到最后一个元素。
4.  然后把新赋值的数组又需要重新赋值给原来数组，有点类似于递归，如此循环重复，直到k的值为0就结束循环。

class Solution {
        public void rotate(int[] nums, int k) {
               if(k == 0){
                nums = nums;
    //            for (int i = 0; i < nums.length; i++) {
    //                System.out.print(nums[i] + "  ");
    //            }
    //            System.out.println();
            }else{
                int len = nums.length-1;
                int[] a = new int[nums.length];
                while (k!=0){
                    a[0] = nums[len];
                    for (int i = 0,j=1; i < len; i++,j++) {
                        a[j] = nums[i];
                    }
                    k--;
                    for (int i = 0; i < a.length; i++) {
                        nums[i] = a[i];
                    }
                }
    //            for (int i = 0; i < nums.length; i++) {
    //                System.out.print(nums[i] + "  ");
    //            }
    //            System.out.println();
            }
        }
    }

运行结果：

Runtime: 121 ms, faster than 5.18% of Java online submissions for Rotate Array.
    Memory Usage: 38.2 MB, less than 30.26% of Java online submissions for Rotate Array.

看一下这个大神的解题思路，我感觉算法题主要是思路，如果思路不对，考虑情况不全，那么选再好的数据结构也不能100%通过test case。

他的思路就是：

1.  先把整个数组翻转
2.  然后对于指定的位置以前的前半部分数组翻转
3.  最后对于后半部分的数组进行翻转

这个算是一种算法思想吧。。。。

public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

这个是另外一种算法，首先根据给定的k，然后计算一下把一部分数值是固定的，赋给数组，然后对于余留的那部分数组值进行循环，每次循环都会出现一个新的小数组，然后继续下去就会成为题目要求的。  
关键点在于循环条件的发现：举个例子来说，比如\[1,2,3,4,5,6,7\] k=3，  
（1） 第一次循环结果就是\[7,6,5,1,2,3,4\] 然后下一次对\[7,6,5\]进行循环，成为\[6,5,7\]；然后对\[6,5\]进行循环，得到\[5,6\]，最终答案就是\[5,6,7,1,2,3,4\]

class Solution {
        public void rotate(int[] nums, int k) {
            if (nums.length == 0) return;
    	    int n = nums.length;
    	    while ((k %= n) > 0 && n > 1) {
    	        int range = n - k;
    	        for (int i = 1; i <= range; i++) {
    	            int val = nums[n - i];
    	            nums[n - i] = nums[n - i - k];
    	            nums[n - i - k] = val;
    	        }
    	        n = k;
    	        k = n - (range % k);
    	    }
        }
    }

上面的算法（除了我的以外），基本都是在时间复杂度优胜于我，尤其是第一个极容易理解，而且可以说写的很漂亮，很值得学习。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20211213/70b02d03255f4099a07cf2ee8a7aa288.png