本文共 1202 字，大约阅读时间需要 4 分钟。

为了恢复一个旋转排序数组到有序状态，我们可以使用三步翻转法。该方法的时间复杂度为O(n)，并且只需O(1)的额外空间。以下是详细的步骤：

以下是实现代码：

class Solution:
    def recoverRotatedSortedArray(self, nums):
        if not nums:
            return nums
        l = len(nums)
        # 找到旋转点i
        i = 0
        while i < l - 1:
            if nums[i] > nums[i+1]:
                break
            i += 1
        if i == l - 1:
            # 数组已经排好序
            return nums
        # 反转0到i
        self.reverse_subarray(nums, 0, i)
        # 反转i+1到l-1
        self.reverse_subarray(nums, i+1, l-1)
        # 反转整个数组
        self.reverse_subarray(nums, 0, l-1)
        return nums
    def reverse_subarray(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1

示例测试：

nums = [4, 5, 1, 2, 3]
solution = Solution()
solution.recoverRotatedSortedArray(nums)
print(nums)  # 输出: [1, 2, 3, 4, 5]

代码解释：

这种方法确保了在O(n)时间和O(1)额外空间内完成任务，适用于所有旋转排序数组。

转载地址：http://kvgfk.baihongyu.com/