檢查給定的陣列在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 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習