LintCode - 恢复旋转排序数组（普通）

版权声明：本文为博主原创文章，未经博主允许不得转载。

难度：容易

要求：

给定一个旋转排序数组，在原地恢复其排序。

说明
什么是旋转数组？
比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

样例

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

思路：

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        if(nums == null || nums.size() == 0){
            return;
        }
        int size = nums.size();
        
        for (int i = 0; i < size - 1; i++) {
            if (nums.get(i) > nums.get(i + 1)) {
                reverse(nums, 0, i);
                reverse(nums, i + 1, size - 1);
                reverse(nums, 0, size - 1);
                return;
            }
        }
    }
    
    private void reverse(ArrayList<Integer> nums, int i, int j) {
        for (; i < j; i++, j--) {
            swap(nums,i,j);
        }
    }

    public static void swap(List<?> list, int i, int j) {
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }
}