在 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

Arnab Chakraborty

更新于: 2020年8月20日

318 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习