Recover Rotated Sorted Array

Source

• lintcode: 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]

Python

class Solution:
    """
    @param nums: The rotated sorted array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        # write your code here
        n= len(nums)
        pos=1
        while pos<n:
            if nums[pos]<nums[pos-1]:
                break
            else:
                pos+=1

        self.reverse(nums, 0, pos-1)
        self.reverse(nums, pos, n-1)
        self.reverse(nums, 0, n-1)

    def reverse(self, nums, left, right):
        while left<right:
            tmp = nums[left]
            nums[left] = nums[right]
            nums[right] = tmp

            left+=1
            right-=1