+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-04(1)

2019-06(2)

2019-07(2)

2019-08(87)

2019-09(90)

LeetCode 581 最短无需连续子数组 Python

发布于2020-07-31 23:02     阅读(833)     评论(0)     点赞(15)     收藏(3)


好久不刷Leetcode,感觉自己编程能力有点拉胯,今天一到简单题目写的很累,关键还是数组的边界问题老是搞糊涂。

问题

给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

你找到的子数组应是最短的,请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

主要思路还是参照官方给出的几种方法,不过官方是java的。我这里主要给出我的理解还有在把思路转换成code时候容易犯的一些错误。

一、暴力法

暴力法也就是穷举法,但是感觉这个暴力法不是很容易想到,我也是看了答案才发现的。当然这个答案是超时的,但是还是很有意思的。
简单的讲就是我们把数组分成三块,前后两块是有序的,中间那块是无序的,我们只需要找出最短的无序数组长度即可。因此使用两个标记,两次遍历循环,约束条件如下:

  1. 前后两块都需要满足有序
  2. 前一块数组的最后一个元素需要小于中间无序数组的最小值
  3. 后一块数组的第一个元素需要大于中间无序数组的最大值

代码如下

import sys
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        res = n = len(nums)
        for i in range(n):  #[0 : n-1]
            for j in range(i, n + 1): #[0 : n]  注意这里是 n + 1, 因为下面的边界是到j
                max_ = prev = -sys.maxsize - 1
                min_ = sys.maxsize 
                for k in range(i, j):  #[0 : n -1]
                    min_, max_  = min(min_, nums[k]), max(max_, nums[k]) # 取[i, j]最大最小值
                if (i > 0 and nums[i-1] > min_) or (j < n and nums[j] < max_):
                    continue  # 当前i,j 区间内的数组不符合条件  跳到下一个i,j区间
                k = 0
                while(k < i and prev <= nums[k]):
                    prev = nums[k]
                    k += 1
                if k != i:
                    continue #同上

                k = j
                while(k < n and prev <= nums[k]):
                    prev = nums[k]
                    k += 1
                if k == n:    # 满足所有条件
                    res = min(j - i, res)  

        return res

注意我们设定的中间一块范围是[i, j)nums[j]是取不到的,所以最后返回j - i而不是j - i +1.

二、improved-暴力法

上述算法复杂度为O(n3) O(n^3),除了两个确定两个标记需要遍历两次,其中还需要判断是否有序。那么我们能否优化掉判断子数组是否有序,从而降低复杂度呢。

如果说第一种方法是“两边夹中间”,也就是确定前一块有序数组和后一块有序数组从而确定两个标记。那么我们可以反过来想,我们只需要确定中间的数组是无序的最大数组,也就得到了两个标记。

因此我们设定两个标记,leftright,分别标记左边界和右边界。初始值分别为len(sum)0,也就是从leftright不构成数组。我们同样通过两次遍历[0,k][k+ 1, len(sum))来更新,我们设这两次循环到的点分别为iji<j<len(sum)它们的更新条件如下:

如果存在nums[j]nums[i]小,这意味着 nums[i]nums[j] 都不在排序后数组中的正确位置,换句话说,它们俩肯定在无序数组中,也即是ij已经构成了一个无序数组,这两个元素标记着目前无序数组的边界。

因此对于每个i,我们都将其与后面的元素进行比较,并且不断更新边界。所以需要两次遍历,时间复杂度为O(n2) O(n^2)

代码如下:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = n, 0
        for i in range(n - 1): #[0, n-2]
            for j in range(i + 1, n): #[i, n-1]
                if nums[j] < nums[i]:
                    right = max(right, j)
                    left = min(left, i)
        return 0 if right - left < 0 else right - left + 1

注意这里i的边界是[0, n-2],因为i=n-2的时候,j就在最右端了,也就把所有情况比较完了。

三、再improve一下

我们知道排序算法的时间复杂度为0(logn) 0(logn),那么根据上面的分析,我们先排序,找出两个数组最左边和最右边元素不相同的坐标,不就能得出我们想要的解。缺点就是空间复杂度太高,上面两种都是O(1) O(1).。

代码很直观:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = n, 0
        snums = nums[:]
        snums.sort()
        for i in range(n): #[0, n-2]
            if snums[i] != nums[i]:
                right = max(right, i)
                left = min(left, i)
        return 0 if right - left < 0 else right - left + 1

下面介绍时间复杂度为O(n) O(n)的两种方法,

四、栈

假设数组不是有序的,并且我们已经按要求分割成三块,[0, i], [i +1, j-1], [j, n-1]。我们思考一个问题,也就是i+1j-1位置上正确的元素应该是什么。很明显,他们分别是中间无序数组中的最小值和最大值,也就是说,我们只要找到这两个元素对应的位置,也就找到了解。

那么怎么找这两个位置,以左边界为例,我们从左向右遍历,当当前元素和前一元素不满足升序的时候,也就意味着左边界位置正确的元素就在当前元素及其后面的范围内了,那么我们只需要找到后面最小的元素,然后拿它去前面元素进行对照即可。

其实不使用栈我们也是可以通过两次遍历实现的,第一次找到标记和后方最小值,第二次在标记前的数组进行比较即可,这样还节省了空间。使用栈可能更为直观。同样以左边界为例,把数组下标一次压进栈,然后当当前元素小于栈顶下标对应元素,栈顶元素出栈,并更新边界。出栈的最小下标值即是左边界,右边界同理。

代码如下;

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        stack = []
        left, right = n, 0
        for i in range(n):
            while(stack and nums[i] < nums[stack[-1]]):
                left = min(left, stack.pop())
            stack.append(i)
        stack = []
        for i in range(n-1, -1, -1):
            while(stack and nums[i] > nums[stack[-1]]):
                right = max(right, stack.pop())
            stack.append(i)
        return 0 if right - left < 0 else right - left + 1

不用栈的代码如下:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        ## 找边界
        for i in range(n-1):
            if(nums[i] > nums[i + 1]):
                label = i + 1
                break
            if i  == n - 2:
                return 0
        l_min =  nums[label]
       	## 找最小元素及位置
        for i in range(label, n):
            l_min = min(l_min, nums[i])
        for i in range(label):
            if l_min < nums[i]:
                left = i 
                break

        for i in range(n-2, -1, -1):
            if(nums[i + 1] < nums[i]):
                label = i
                break
        r_max =  nums[label]
        
        for i in range(label, -1, -1):
            r_max = max(r_max, nums[i])
        for i in range(n-1, label, -1):
            if r_max > nums[i]:
                right = i 
                break

        return 0 if right - left < 0 else right - left + 1

原文链接:https://blog.csdn.net/d8212137/article/details/107677662



所属网站分类: 技术文章 > 博客

作者:智慧星辰

链接: https://www.pythonheidong.com/blog/article/467252/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

15 0
收藏该文
已收藏

评论内容:(最多支持255个字符)