Python程序检查数组是否已排序并旋转

假设我们有一个名为nums的数组，我们需要检查该数组是否最初按非递减顺序排序，然后旋转了一些位置（可能是零）还是没有。数组中也可能存在重复项。

因此，如果输入类似于nums = [12,15,2,5,6,9]，则输出将为True，因为它向右旋转了两个位置。

为了解决这个问题，我们将遵循以下步骤：

• j := 0

• 当 j < nums 的大小 - 1 且 nums[j] <= nums[j + 1] 时，执行

  • j := j + 1

• res := （从索引 j + 1 到 nums 结尾的 nums 的子数组）连接（从索引 0 到 j 的 nums 的子数组）

• 对于 i 从 0 到 res 的大小 - 1，执行

  • 如果 res[i] > res[i + 1]，则

    • 返回 False

• 返回 True

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

def solve(nums):
   j = 0
   while (j < len(nums) - 1 and nums[j] <= nums[j + 1]):
      j += 1
   res = nums[j + 1 : len(nums)] + nums[0:j + 1]
   for i in range(len(res) - 1):
      if res[i] > res[i + 1]:
         return False
   return True

nums = [12,15,2,5,6,9]
print(solve(nums))

输入

[12,15,2,5,6,9]

输出

True

Arnab Chakraborty

更新于: 2021年5月18日

425 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习