檢查在 Python 中是否可以透過允許交換相鄰元素來排序陣列

假設我們有一個無序的數字陣列，稱為 nums，所有元素都在 0 到 n-1 的範圍內。我們可以根據需要多次交換 nums 中的相鄰元素，但只有當這些元素之間的絕對差為 1 時才可以。我們必須檢查是否可以對 nums 進行排序。

因此，如果輸入類似於 nums = [1, 0, 3, 2, 5, 4]，則輸出將為 True，因為我們可以交換這些對 [(1, 0), (3, 2), (5, 4)] 以排序 [0, 1, 2, 3, 4, 5]。

為了解決這個問題，我們將遵循以下步驟：

  • 對於 i 從 0 到 nums 的大小 - 2，執行：
    • 如果 nums[i] > nums[i+1]，則：
      • 如果 nums[i] - nums[i+1] 等於 1，則：
        • 交換 nums[i] 和 nums[i+1]
      • 否則：
        • 返回 False
  • 返回 True

示例

讓我們來看下面的實現，以便更好地理解：

 線上演示

def solve(nums):
   for i in range(len(nums) - 1):
      if nums[i] > nums[i+1]:
         if nums[i] - nums[i+1] == 1:
            nums[i], nums[i+1] = nums[i+1], nums[i]
         else:
            return False
   return True
nums = [1, 0, 3, 2, 5, 4]
print(solve(nums))

輸入

[1, 0, 3, 2, 5, 4]

輸出

True

更新於：2021年1月19日

235 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始
廣告