最短子数组

谁借莪１个温暖的怀抱￠ 2022-06-09 01:55 152阅读 0赞

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。

给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列有序，返回0)。保证A中元素均为正整数。

# 测试样例：
    [1,4,6,5,9,10],6
    返回：2

> 解题参考 ：[http://blog.csdn.net/u010033948/article/details/51396354][http_blog.csdn.net_u010033948_article_details_51396354]

**我的提交**

# -*- coding:utf-8 -*-
    
    class Subsequence:
        def shortestSubsequence(self, A, n):
            # write code here
            maxValue = A[0]
            maxErrIndex = -1
            for i in range(n):
                if A[i] > maxValue:
                    maxValue = A[i]
                elif A[i] < maxValue:
                    maxErrIndex = i
    
            if maxErrIndex == -1:
                return 0
            minValue = A[n-1]
            minErrIndex = -1
            for j in range(n)[::-1]:
                if A[j] < minValue:
                    minValue = A[j]
                elif A[j] > minValue:
                    minErrIndex = j
    
            return maxErrIndex - minErrIndex + 1
    
    if __name__ == '__main__':
        s = Subsequence()
        print(s.shortestSubsequence([1,2,10,1,8,9],6))

[http_blog.csdn.net_u010033948_article_details_51396354]: http://blog.csdn.net/u010033948/article/details/51396354

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-581. 最短无序连续子数组

题目来源 [581. 最短无序连续子数组][581.] 题目分析从左往右遍历，缓存最大值，记录最右的不符合的值，只能确定最右的数排序不会动，确定右边界。从右往左遍

太过爱你忘了你带给我的痛/ 2024年03月29日 16:26/ 0 赞/ 49 阅读

相关 C语言重构【581】最短无序连续子数组

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

约定不等于承诺〃/ 2022年12月19日 06:13/ 0 赞/ 107 阅读

相关 581. 最短无序连续子数组

题目： [581. 最短无序连续子数组][581.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_1

àì夳堔傛蜴生んèń/ 2022年12月02日 04:30/ 0 赞/ 90 阅读

相关最短覆盖子串

/ 给两个字符串S和T，请在S中找到包含T中全部字符的最短子串 / public class Solution { public

爱被打了一巴掌/ 2022年10月29日 07:55/ 0 赞/ 142 阅读

相关 Leetcode581. 最短无序连续子数组

题目难度：中等题目描述： > 给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 > > 请你找

痛定思痛。/ 2022年09月08日 11:52/ 0 赞/ 131 阅读

相关 581 最短无序连续子数组（区间问题）

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

╰+哭是因爲堅強的太久メ/ 2022年08月31日 11:20/ 0 赞/ 131 阅读

相关最短子数组

对于一个数组，请设计一个高效算法计算需要排序的最短子数组的长度。给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的长度。(原序列位置从0开始标号,若原序列

谁借莪１个温暖的怀抱￠/ 2022年06月09日 01:55/ 0 赞/ 153 阅读

相关最短无序连续子数组

题目描述给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。示例

桃扇骨/ 2022年01月25日 16:09/ 0 赞/ 230 阅读

相关【leetCode】第581题：最短无序连续子数组

LeetCode 链接：[https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/][ht

川长思鸟来/ 2021年12月11日 18:59/ 0 赞/ 184 阅读

相关【搞定算法】需要排序的最短子数组长度

> 题目：给定一个无序数组 arr，求出需要排序的最短子数组长度。例如：arr = \[1，5，3，4，2，6，7\] 返回 4，因为只有 \[5，3，4，2\] 需要排序。

水深无声/ 2021年11月23日 01:46/ 0 赞/ 202 阅读