Rotate Array

Leave a comment

November 27, 2016 by oneOokay

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.


  • array: 1,2,3,4,5  ->  k = 2 -> 4,5,1,2,3.
  • (1,2,3),(4,5) VS (4,5),(1,2,3) =>其实就是把前len – k个数与后k个数swap了一下。这里可以直接写出一个解法了。
  • 但是接下来可以进一步优化成inplace的:继续看一下,分块reverse的话变成了:(5,4),(3,2,1)。所以就可以用reverse 的方法来inplace的做。具体步骤如下
    1. reverse 原array
    2. reverse array中0 到k-1的元素
    3. reverse array中k到最后一个元素

还要注意一下k的简化。

相关问题是:Reverse Words in a String II

第一个swap的解法,主要注意的是各种下标,先标出下标来感觉好些一些:

  • 开始:(O[0],…,O[len-k-1]),(O[len – k], …,O[len-1])
  • 结束:(O[0],…,O[k-1]),(O[k],…,O[len-1])
public class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        if (nums == null || len <= 1){
            return;
        }
        
        if (k % len == 0){
            return;
        }
        
        k = k % len;
        int[] tmp = new int[k];
        for (int i = 0; i < k; i ++){
             tmp[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] = tmp[i];
        }
    }
}

inplace的最优解法:

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1){
            return;
        }
        
        if (k % nums.length == 0){
            return;
        }
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    
    private void reverse(int[] nums, int start, int end){
        while (start < end){
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start ++;
            end --;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: