Reorder Rotated Array

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

样例

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

挑战

使用O(1)的额外空间和O(n)时间复杂度

说明

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

Solution

首先找到分割点,随后分三步调用翻转函数。

Complexity

时间复杂度 O(n),哦那感觉复杂度 O(1)

Code

class Solution:
    """
    @param nums: The rotated sorted array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        # write your code here
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                self.recover(nums, 0, i)
                self.recover(nums, i+1, len(nums)-1)
                self.recover(nums, 0, len(nums) -1)
        return

    def recover(self, nums, start, end):
        i, j = start, end
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i = i + 1
            j = j - 1
        return nums