平移数组 Rotate Array

      前两天在leetcode上刷题，无意中做了这么个小问题觉得值得反思一下。

 

      题目很简单：Rotate an array of n elements to the right by k steps.  For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

      Note : Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

 

       首先想到最简单的实现方法，循环拿到数组的最后一个元素，然后把所有其他元素后移一位，再把之前的最后一个元素放在第一位，这方法简单粗暴，但是资源浪费严重，两重循环一旦input元素很大，效率实在低下。还是贴上代码：

 

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

 基本没啥技术含量，感觉就是面试的时候突然感觉智商没了的话，起码写点什么。。。

 

 

那么下一步想的是如何减少循环嵌套，只用一遍循环解决这个问题，其实很简单，稍微观察下就能知道所谓的右移无非就是把第 length(数组长度)-k(右移个数) 到最后一个元素拼到第一个元素之前。说白了就是从后往前数第K个元素拉到最前面。这样的话毫无疑问得再动用另一个数组作为缓存。代码如下（仍需优化）

 

public class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        
        if(len<2||len==k){
            return;
        }
        
        if(k>len){
            k=k%len;
        }
        int[] copy = new int[len];
        for(int i=0;i<k;i++){
            copy[i] = nums[len-k+i];
        }
        
        for(int j=0;j<len-k;j++){
            copy[k+j] = nums[j];
        }
        for(int m = 0;m<len;m++){
            nums[m] = copy[m];
        }
    }
}

 肯定跑过，而且执行效率在Java里也算是靠前的。

 

 

目前还在想怎么把执行效率再提高一点，不过就方法来说，在leetcode有位同学的方法还是挺值得借鉴的，主要是我特别喜欢这种代写的特别清楚明白O(n) time and O(1)space，不过速度还是比我的差一点点~：

 

public class Solution {
    public void rotate(int[] nums, int k) {
       int end = nums.length;
        k=k%end;// to check for outofbounds when k >= nums.length
        rotate(nums,0,end-k-1);//reverse one half of the array
        rotate(nums,end-k,end-1);//reverse other half of the array
        rotate(nums,0,end-1);//reverse whole array  
    }
    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    public void rotate(int[] nums,int start,int end){
        for(int i = start;i<=(start+end)/2;i++){
            swap(nums,i,(start+end)-i);
        }
    }
}

 

 

虽然这是个小问题，但是我觉得时刻多一个问题多几分想法，还是很有必要的