在 Python 中查詢使整個陣列排序的最小長度未排序子陣列

假設我們有一個給定的未排序陣列 A[0..n-1]，大小為 n，我們需要找到最小長度的子陣列 A[s..e]，以便透過對該子陣列進行排序，整個陣列將被排序。所以，如果陣列類似於 [2,6,4,8,10,9,15]，那麼輸出將是 5。子陣列將是 [6,4,8,10,9]。

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

  • res := 將 nums 作為陣列排序

  • ans := 0

  • 將 r 設定為連結串列

  • 對於 i 從 0 到 res 的長度

    • 如果 nums[i] 與 res[i] 不相同，則將 i 插入到 r 中

  • 如果 r 的長度為 0，則返回 0，如果 r 的長度為 1，則返回 1

  • 返回 r 的最後一個元素 - r 的第一個元素 + 1

示例

讓我們看看以下實現以獲得更好的理解：

即時演示

class Solution(object):
   def findUnsortedSubarray(self, nums):
      res = sorted(nums)
      ans = 0
      r = []
      for i in range(len(res)):
         if nums[i] != res[i]:
            r.append(i)
      if not len(r):
         return 0
      if len(r) == 1:
         return 1
      return r[-1]-r[0]+1
ob1 = Solution()
print(ob1.findUnsortedSubarray([2,6,4,8,10,9,15]))

輸入

[2,6,4,8,10,9,15]

輸出

5

更新於: 2020年8月20日

318 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告