检查反转子数组是否使 Python 中的数组排序

假设我们有一个名为 nums 的数组，其中包含唯一元素。我们必须检查在反转其一个子数组后，数组是否将被排序。如果数组已经排序，则也返回 True。

因此，如果输入类似于 nums = [4,6,27,25,15,9,37,42]，则输出将为 True，因为如果我们反转 [9,15,25,27]，则数组将被排序。

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

• n := nums 的大小
• 如果数组只有一个元素，则返回 True
• i := 1
• 对于 i 的范围从 1 到 n - 1，执行以下操作
  • 如果 nums[i - 1] < nums[i]，则
    • 如果 i 与 n 相同，则返回 true，否则退出循环
• j := i
• 当 j < n 且 nums[j] < nums[j - 1] 时，执行以下操作
  • 如果 i > 1 且 nums[j] < nums[i - 2]，则返回 false
  • j := j + 1
• 如果 j 与 n 相同，则返回 True
• k := j
• 如果 nums[k] < nums[i - 1]，则返回 False
• 当 k > 1 且 k < n 时，执行以下操作
  • 如果 nums[k] < nums[k - 1]，则返回 False
  • k := k + 1
• 返回 True

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

示例代码

在线演示

def solve(nums):
   n = len(nums)
   if n == 1:
      return True
 
   i = 1
   for i in range(1, n):
      if nums[i - 1] < nums[i] :
         if i == n:
           return True
      else:
         break
   j = i
   
   while j < n and nums[j] < nums[j - 1]:
      if i > 1 and nums[j] < nums[i - 2]:
         return False
      j += 1
 
   if j == n:
      return True
 
   k = j
   if nums[k] < nums[i - 1]:
      return False
 
   while k > 1 and k < n:
      if nums[k] < nums[k - 1]:
         return False
      k += 1
   return True

nums = [4,6,27,25,15,9,37,42]
print(solve(nums))

输入

[4,6,27,25,15,9,37,42]

输出

True

Arnab Chakraborty

更新于: 2021年1月15日

253 次查看

开启你的 职业生涯

通过完成课程获得认证

开始