在 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]

输出

5

更新于： 2020 年 4 月 27 日

226 次浏览

开启你的职业

通过完成课程取得认证

入门
广告