Problem

Given a rotated sorted array, recover it to sorted array in-place.

Clarification
What is rotated array?

For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
Example
[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

思路

• 三步反转
• 找到rotated index i
• 翻转 (0, i)
• 翻转(i + 1, end)
• 翻转(0, end)

    /*
        1. find the index of max value
        2. if the index < len - 1
                rotate the array before and include the index
            else do nothing
        3. rotate the whole array
    */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        if (nums == null || nums.size() <= 1) {
            return;
        }
        int index = 0;
        for (;index < nums.size() - 1; index++) {
            if (nums.get(index) > nums.get(index + 1)) {
                break;
            }
        }
        rotate(nums, 0, index);
        rotate(nums, index + 1, nums.size() - 1);
        rotate(nums, 0, nums.size() - 1);
    }

    private void rotate(ArrayList<Integer> nums, int start, int end) {
        while (start < end) {
            int temp = nums.get(start);
            nums.set(start, nums.get(end));
            nums.set(end, temp);
            start++;
            end--;
        }
    }