恢复旋转排序数组
题目描述
给定一个旋转排序数组，在原地恢复其排序。
比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
样例
Example1: [4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5] Example2: [6,8,9,1,2] -> [1,2,6,8,9]
挑战
使用O(1)的额外空间和O(n)时间复杂度。
思路
找到旋转位置index，然后3次翻转：先翻转index前面部分，再翻转index后面部分，最后翻转整个数组。
例如：[4, 5, 1, 2, 3]，找到index=2，翻转[4,5]为[5,4]，翻转[1,2,3]为[3,2,1]，最后翻转[5,4,3,2,1]为[1,2,3,4,5]
代码
def recoverRotatedSortedArray(nums): # write your code here n = len(nums) #找min_index min_index = 0 for i in range(n-1): if nums[i] > nums[i+1]: min_index = i+1 break #翻转nums[0:min_index] for j in range(min_index//2): nums[j],nums[min_index-1-j] = nums[min_index-1-j],nums[j] #翻转nums[min_index:] for k in range((n-min_index)//2): nums[min_index+k],nums[n-1-k] = nums[n-1-k],nums[min_index+k] #翻转nums[:] for m in range(n//2): nums[m],nums[n-1-m] = nums[n-1-m],nums[m]