RotateArray [source code]

public class RotateArray {
static
/******************************************************************************/
public class Solution {
    public void rotate(int[] nums, int k) {
        rotate(nums, 0, nums.length - 1, k);
    }

    public void rotate(int[] nums, int lo, int hi, int k) {
        int n = hi - lo + 1;
        if (k >= n) k = k % n;
        if (k <= 0) return;
        if (k == n - k) reverse(nums, lo, hi, k);
        else if (n - k > k) {
            reverse(nums, lo, hi, k);
            rotate(nums, lo + k, hi, k);
        } else {
            reverse(nums, lo, hi, n - k);
            rotate(nums, lo, hi - (n - k), k - (n - k));
        }
    }

    public void reverse(int[] nums, int lo, int hi, int k) {
        int tmp;
        int n = hi - lo + 1;
        if (k > n / 2) return;
        for (int i = 0; i < k; i++) {
            tmp = nums[hi - k + 1 + i];
            nums[hi - k + 1 + i] = nums[lo + i];
            nums[lo + i] = tmp;
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        RotateArray.Solution tester = new RotateArray.Solution();
        int[][] inputs = {
            {1,2,3,4,5,6,7}, {3}, {5,6,7,1,2,3,4},
            {1,2,3,4,5,6,7,8,9,10}, {3}, {8,9,10,1,2,3,4,5,6,7},
            {1}, {0}, {1},
            {1,2}, {3}, {2, 1},
        };
        for (int i = 0; i < inputs.length / 3; i++) {
            int[] nums = inputs[3 * i];
            int k = inputs[1 + 3 * i][0];
            String expected = Printer.array(inputs[2 + 3 * i]);
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(Printer.array(nums));
            Printer.closeColor();
            tester.rotate(nums, k);
            String output = Printer.array(nums);
            System.out.print(" -> " + output);
            Printer.openColor(output.equals(expected) ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

首先仔细读题: 这里的n和k都是length, 而不是index;

刚开始看错题目了, 直接写了这个东西:

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

recursion的算法在debug的时候一个常用技巧就是在每一个call进入的时候把参数print出来;

看起来很简单的一个题目, 结果出乎意料的难写, 花了很长时间才写完. 最后的想法是利用recursion来做, 而且写了两个helper; 中间各种变量的更新的细节处理也并非那么简单, 必须要例子与visual结合来帮助分析.

最后的速度是1ms (13%), 其实不差了, 不过老题目, 最优解太多了;

另外这一题其实我一开始看错题目了, 以为就是从右边量k个, 然后k和n-k对调. 后来处理k >= n的情况的时候才发现这个题目的本意就是从0开始, 把i跟n-i对调, 进行k次. 所以如果k比n大, 直接mod一下就行了; (每n个step, 这个array其实是最后被还原了);

这个速度好像是InPlace的最优解了. 0ms那个实际上就是copy来做的;

另外这一题的bruteforce的做法其实并不难, 直接就是按照题目对于rotate的定义来做就行了. 不过这个做法实际上最后是超时了的, 这个肯定也是OJ故意的;

这个是暴力解的代码:

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

看了这个暴力解才感觉, 我之前对这个rotate的理解其实还是错的, 并不是头和尾, 然后头+1和尾巴-1这样的swap,而是一个类似于cyclical shift这样的rotate;
这个也符合了为什么我的这种先分块再交换的理解是对的原因;
这个理解的改变实际上对于代码的实现并没有影响;

至于非InPlace的做法就不多说了, 上面也讲了, 很好写, 完全没有难度, 直接几个copy就行了;

这个是editorial4:

Original List                   : 1 2 3 4 5 6 7  
After reversing all numbers     : 7 6 5 4 3 2 1  
After reversing first k numbers : 5 6 7 4 3 2 1  
After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

public class Solution {  
    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--;  
        }  
    }  
}

这个方法应该是这个问题最简练的一个方法了. 出发点其实跟我的算法是类似的, 不是用shift来做, 而是只考虑最终的结果, 其实就是长度为n - k跟长度为k的两个subarray对掉了位置(两个subarray内部的顺序不变);

这里的做法其中有一个就是, 当你把整个长度为n的array都reverse一遍的时候, 正好本来在前n-k跟后k个位置的元素也全都正好掉换了位置. 然后两个subarray内部的顺序还原一下就行了;

不得不说这个算法还是比较讨巧的, 短时间内比较难想出来, 我感觉还是我自己的算法比较具有普适性: 我的算法其实就是一个非常典型的recursion算法, divide and conquer.

底下有人说这个算法其实是在programming pearls里面的; 不知道真的假的, 如果是这样, 那我也释然了;

我这个算法, discussion里面果然也有人想出来了, 好写的是一个iterative的版本:

class Solution   
{  
public:  
    void rotate(int nums[], int n, int k)   
    {  
        if ((n == 0) || (k <= 0) || (k%n == 0))  
        {  
            return;  
        }  

        k = k%n;  
        // Rotation to the right by k steps is equivalent to swapping   
        // the two subarrays nums[0,...,n - k - 1] and nums[n - k,...,n - 1].  
        int start = 0;  
        int tmp = 0;  
        while (k > 0)  
        {  
            if (n - k >= k)  
            {  
                // The left subarray with size n - k is longer than   
                // the right subarray with size k. Exchange   
                // nums[n - 2*k,...,n - k - 1] with nums[n - k,...,n - 1].  
                for (int i = 0; i < k; i++)  
                {  
                    tmp = nums[start + n - 2*k + i];  
                    nums[start + n - 2*k + i] = nums[start + n - k + i];  
                    nums[start + n - k + i] = tmp;  
                }  

                // nums[n - 2*k,...,n - k - 1] are in their correct positions now.  
                // Need to rotate the elements of nums[0,...,n - k - 1] to the right   
                // by k%n steps.  
                n = n - k;  
                k = k%n;  
            }  
            else  
            {  
                // The left subarray with size n - k is shorter than   
                // the right subarray with size k. Exchange   
                // nums[0,...,n - k - 1] with nums[n - k,...,2*(n - k) - 1].  
                for (int i = 0; i < n - k; i++)  
                {  
                    tmp = nums[start + i];  
                    nums[start + i] = nums[start + n - k + i];  
                    nums[start + n - k + i] = tmp;  
                }  

                // nums[n - k,...,2*(n - k) - 1] are in their correct positions now.  
                // Need to rotate the elements of nums[n - k,...,n - 1] to the right   
                // by k - (n - k) steps.  
                tmp = n - k;  
                n = k;  
                k -= tmp;  
                start += tmp;  
            }  
        }  
    }  
};

当然, 我用的是recursion, 反映subproblem的变化利用的是参数, 他既然写的是iterative, 利用的就是local var的更新来完成, 这个也是提过很多次了;

关于recursion跟iteration之间的转换, 感觉以后可能会多次碰到. 在这个问题上, Binary Search就是一个非常典型的例子, 分析Binary Search就能得到很多启发. 一般从recursion转换过来的iteration, 都是有两个一头一尾的var来保存iterate的范围, 然后每一个iteration, 这两个范围var都被更新, 对应了每一个recursive call的时候的argument的更新;

好像这个答案才是跟我的做法比较对应的一个做法:

class Solution   
{  
public:  
    void rotate(int nums[], int n, int k)   
    {  
        for (; k = k%n; n -= k, nums += k)  
        {  
            // Swap the last k elements with the first k elements.   
            // The last k elements will be in the correct positions  
            // but we need to rotate the remaining (n - k) elements   
            // to the right by k steps.  
            for (int i = 0; i < k; i++)  
            {  
                swap(nums[i], nums[n - k + i]);  
            }  
        }  
    }  
};

不过他这个写的比较奇怪. 但是思路还是对的好像;

Problem Description

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.

[show hint]

Related problem: Reverse Words in a String II

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

Difficulty:Easy
Total Accepted:130.5K
Total Submissions:534K
Contributor: LeetCode
Companies
microsoft bloomberg
Related Topics
array
Similar Questions
Rotate List Reverse Words in a String II

Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II