检查给定的数组在Python中是否几乎已排序（元素最多相隔一个位置）

假设我们有一个名为nums的数字数组，其中所有元素都是唯一的。我们必须检查nums是否几乎已排序。众所周知，当任何元素最多与其在已排序数组中的原始位置相隔1个距离时，数组几乎已排序。

因此，如果输入类似于nums = [10, 30, 20, 40]，则输出将为True，因为10位于其原始位置，所有其他元素最多与其实际位置相隔一个位置。

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

• i := 0
• 当i < nums的大小 - 1时，执行
  • 如果nums[i] > nums[i + 1]，则
    • 交换nums[i]和nums[i + 1]
    • i := i + 1
  • i := i + 1
• 对于i从0到nums的大小 - 1，执行
  • 如果nums[i] > nums[i + 1]，则
    • 返回False
• 返回True

示例

让我们看看下面的实现来更好地理解：

 在线演示

def solve(nums):
   i = 0
   while i < len(nums) - 1:
      if nums[i] > nums[i + 1]:
         nums[i], nums[i + 1] = nums[i + 1], nums[i]
         i += 1
      i += 1
   for i in range(len(nums) - 1):
      if nums[i] > nums[i + 1]:
         return False
   return True
nums = [10, 30, 20, 40]
print(solve(nums))

输入

[10, 30, 20, 40]

输出

True

Arnab Chakraborty

更新于：2021年1月18日

273 次浏览

开启您的职业生涯

完成课程获得认证

开始学习