在 Python 中尋找最短無序連續子陣列

假設我們有一個整數陣列，我們需要找到這樣一個連續子陣列，如果我們僅按升序對該子陣列進行排序，那麼整個陣列也將被排序。我們需要找到最短的此類子陣列並輸出其長度。因此，如果陣列是 [2,6,4,8,10,9,15]，那麼輸出將為 5。陣列將為 [6,4,8,10,9]

要解決此問題，我們將遵循以下步驟 -

res := 將 nums 作為一個數組進行排序
ans := 0
將 r 設定為連結串列
對於從 0 到 res 長度的 i
- 如果 nums[i] 與 res[i] 不同，則將 i 插入 r
如果 r 的長度為 0，則返回 0；如果 r 的長度為 1，則返回 1
返回 r 的最後元素 – r 的第一個元素 + 1

示例（Python）

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

即時演示

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]

輸出

Arnab Chakraborty

更新於： 2020 年 4 月 27 日

226 次瀏覽

開啟你的職業

透過完成課程取得認證

入門