查找最小长度的未排序子数组,在 Python 中对整个数组进行排序

pythonserver side programmingprogramming更新于 2025/9/30 14:36:17

假设我们有一个给定的未排序数组 A[0..n-1],大小为 n,我们必须找到最小长度的子数组 A[s..e],这样通过对该子数组进行排序,整个数组就会排序。因此,如果数组为 [2,6,4,8,10,9,15],则输出将为 5。子数组为 [6,4,8,10,9]。

为了解决这个问题,我们将遵循以下步骤 −

  • res := 将数字排序为数组

  • 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

相关文章


有用资源