算法随笔_12:最短无序子数组

上一篇: 算法随笔_11: 字符串的排列-CSDN博客

题目描述如下:

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]

输出：5

解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

===================

我们一起来分析一下这道题。

需要找出的这个子数组可以是任意的位置。不失一般性的，我们可以假设这个子数组的起始点在原来数组的中间某处。我们假设这个子数组为nums_mid，那么此时它分割出来左右两个子数组分别为nums_left，nums_right。按照题意，如果对子数组nums_mid进行升序排序，整个数组都会变为升序排序，那么原数组应该有以下的特征:

仅对子数组nums_mid进行升序排序，就相当于对全数组进行了排序。反过来说，对全数组进行排序，其实只是把nums_mid进行了排序。在排序的前后，nums_left，nums_right两个子数组的序列是不变的。

基于此特征，我们可以写出如下算法:

我们对原数组进行升序排序。排序之后，我们把排序之后的数组与原数组从左到右逐个字符的进行比较。当发现第一个出现不同的字符时，我们就找到了nums_left。同理，从右至左逐个字符的进行比较，我们就找到nums_right。那么，中间的这一块儿就是nums_mid。其长度即可算出。

此算法的时间复杂度为O(nlogn) 。

==================

让我们再考虑一下有没有更优的算法？

让我们重新审视一下原题的描述。nums_mid不论是否排序，它里面的任何一个元素都比nums_left中的任何一个元素大。nums_right在排序前后本身就不改变序列，因此，它的任何一个元素也比nums_left的任何一个元素大。因此，nums_left有如下特征:

1. 它是一个升序排列。

2. 它的最大值一定比后面所有数的最小值还要小。

基于此特征，我们可以给出如下的算法:

1. 我们设置两个变量，nums_left_max(表示nums_left的最大值的下标)，和left_min(表示nums_left后面所有数的最小值)。

2. 我们从右向左遍历原数组，记录当前已经遍历过的元素的最小值left_min。并且每个当前访问的元素e和left_min比较，会有下面两种情况:

   a. 如果e小于left_min，并且nums_left_max为-1，我们记录当前下标为nums_left_max。

   b. 如果e大于left_min，那么nums_left_max肯定不为当前的下标。我们把nums_left_max重置为1。

遍历完成后我们就找到了nums_left_max。

同理，我们可以求出nums_right_min(表示nums_right的最小值的下标)。

最终两数相减即为题目答案。由于此算法只执行了一次遍历，因此时间复杂度为O(N) 。

算法具体实现时注意一下边界条件。实际代码如下:

class Solution(object):def findUnsortedSubarray(self, nums):n=len(nums)nums_left_max=-1nums_right_min=nleft_min=float('inf')right_max=float('-inf')for i in range(n):if right_max<=nums[i]:right_max=nums[i]if nums_right_min==n:nums_right_min=ielse:nums_right_min=nif left_min>=nums[n-i-1]:left_min=nums[n-i-1]if nums_left_max==-1:nums_left_max=n-i-1else:nums_left_max=-1ret=nums_right_min-nums_left_max-1ret=0 if ret<0 else retreturn ret