Python 中最短的未排序连续子数组

pythonserver side programmingprogramming更新于 2025/10/25 8:12:17

假设我们有一个整数数组，我们需要找到一个连续子数组，这样，如果我们只按升序对该子数组进行排序，那么整个数组也会排序。我们需要找到最短的此类子数组并输出其长度。因此，如果数组为 [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

示例 (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]))