Recover Rotated Sorted Array详解编程语言

Given a rotated sorted array, recover it to sorted array in-place. 
 
Example 
[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5] 
 
Challenge 
In-place, O(1) extra space and O(n) time. 
 
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]

public class Solution { 
    /** 
     * @param nums: The rotated sorted array 
     * @return: The recovered sorted array 
     */ 
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) { 
        if (nums == null || nums.size() <= 1) { 
            return; 
        } 
 
        int pos = 1; 
        while (pos < nums.size()) { // find the break point 
            if (nums.get(pos - 1) > nums.get(pos)) { 
                break; 
            } 
            pos++; 
        } 
        myRotate(nums, 0, pos - 1); 
        myRotate(nums, pos, nums.size() - 1); 
        myRotate(nums, 0, nums.size() - 1); 
    } 
 
    private void myRotate(ArrayList<Integer> nums, int left, int right) { // in-place rotate 
        while (left < right) { 
            int temp = nums.get(left); 
            nums.set(left, nums.get(right)); 
            nums.set(right, temp); 
            left++; 
            right--; 
        } 
    } 
}

/** 
 * forked from 
 * http://www.jiuzhang.com/solutions/recover-rotated-sorted-array/ 
 */ 
class Solution { 
private: 
    void reverse(vector<int> &nums, vector<int>::size_type start, vector<int>::size_type end) { 
        for (vector<int>::size_type i = start, j = end; i < j; ++i, --j) { 
            int temp = nums[i]; 
            nums[i] = nums[j]; 
            nums[j] = temp; 
        } 
    } 
 
public: 
    void recoverRotatedSortedArray(vector<int> &nums) { 
        for (vector<int>::size_type index = 0; index != nums.size() - 1; ++index) { 
            if (nums[index] > nums[index + 1]) { 
                reverse(nums, 0, index); 
                reverse(nums, index + 1, nums.size() - 1); 
                reverse(nums, 0, nums.size() - 1); 
 
                return; 
            } 
        } 
    } 
};