假设我们有一个名为 nums 的数组,其中包含唯一元素。我们必须检查数组在反转它的一个子数组后是否会被排序。如果数组已经排序,则也返回 true。
因此,如果输入类似于 nums = [4,6,27,25,15,9,37,42],那么输出将为 True,因为如果我们反转 [9,15,25,27],则数组将被排序。
为了解决这个问题,我们将按照以下步骤操作 -
n := 数字的大小
如果数组只有一个元素,则返回 True
我:= 1
对于 1 到 n - 1 范围内的 i,请执行
如果 i 与 n 相同,则返回 true,否则从循环中出来
如果 nums[i - 1] < nums[i],则
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
返回真
让我们看看以下实现以获得更好的理解 -
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