leetcode 189. Rotate Array

2017-08-07

题意

旋转数组，打个比方数组长 [1,2,3,4,5,6,7]，旋转数字k = 3,经过旋转 [5,6,7,1,2,3,4].

我的思路

最蠢的办法：每次拿出数组的最后一个数字，然后把整个数组往后移动一位。遍历k次。

这种办法是超时的。

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

想了想还有别的办法：利用空间缩短了时间效率。

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

大神代码

大神实现了一个反转数组的函数，首先反转全部数组。然后把前k项反转，最后把后n-k项反转。

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--;
    }
}