Python程式檢查陣列是否已排序並旋轉

假設我們有一個名為nums的陣列，我們需要檢查該陣列是否最初按非遞減順序排序，然後旋轉了一些位置（可能是零）還是沒有。陣列中也可能存在重複項。

因此，如果輸入類似於nums = [12,15,2,5,6,9]，則輸出將為True，因為它向右旋轉了兩個位置。

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

  • j := 0

  • 當 j < nums 的大小 - 1 且 nums[j] <= nums[j + 1] 時，執行

    • j := j + 1

  • res := （從索引 j + 1 到 nums 結尾的 nums 的子陣列）連線（從索引 0 到 j 的 nums 的子陣列）

  • 對於 i 從 0 到 res 的大小 - 1，執行

    • 如果 res[i] > res[i + 1]，則

      • 返回 False

  • 返回 True

示例（Python）

讓我們看看以下實現以更好地理解：

 線上演示

def solve(nums):
   j = 0
   while (j < len(nums) - 1 and nums[j] <= nums[j + 1]):
      j += 1
   res = nums[j + 1 : len(nums)] + nums[0:j + 1]
   for i in range(len(res) - 1):
      if res[i] > res[i + 1]:
         return False
   return True

nums = [12,15,2,5,6,9]
print(solve(nums))

輸入

[12,15,2,5,6,9]

輸出

True

更新於: 2021年5月18日

425 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告