美文网首页
需要排序的最短子数组长度

需要排序的最短子数组长度

作者: 钢筋铁骨 | 来源:发表于2020-04-19 22:18 被阅读0次

例如:
[1,4,5,3,2,8]
返回4,解释:需要排序的是[4,5,3,2]

思路:
双指针操作
从左边遍历,找出不合理的位置,此位置为right_index
从右边遍历,找出不合理的位置,此位置为left_index
right_index - left_index + 1

class Solution(object):
    def run(self, lst):
        n = len(lst)
        _max = lst[0]
        for i in range(0, n):
            if lst[i] > _max:
                _max = lst[i]
            else:
                k = i # k是需要排序的最右边的index
        print ("k=", k)

        _min = lst[-1]
        for i in range(n-1, 0, -1):
            if lst[i] < _min:
                _min = lst[i]
            else:
                j = i # j是需要排序的最左边的index
        print ("j=", j)
        return k-j+1

lst = [1,4,5,3,2,8]
s =Solution()
print (s.run(lst))

相关文章

  • 2.2.3 无序数组需要排序的最短子数组

    对于一个无序数组A,请设计一个算法,求出需要排序的最短子数组的长度。 给定一个整数数组A及它的大小n,请返回最短子...

  • 需要排序的最短子数组长度

    例如:[1,4,5,3,2,8]返回4,解释:需要排序的是[4,5,3,2] 思路:双指针操作从左边遍历,找出不合...

  • 待排序的最短子数组

    题目 对于一个数组,请设计一个高效算法计算需要排序的最短子数组的长度。给定一个int数组A和数组的大小n,请返回一...

  • 2_19最短子数组

    对于一个数组,请设计一个高效算法计算需要排序的最短子数组的长度。 给定一个int数组A和数组的大小n,请返回一个二...

  • LeetCode 862. 和至少为 K 的最短子数组

    返回 A 的最短的非空连续子数组的长度,该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组,返回 -1。...

  • 3.数组中重复的数字

    找出数组中任意一个重复的数字! 思路1:把数组排序,从排序后的数组中找出重复的数字。但排序一个长度为n的数组需要O...

  • LeetCode 第 442 题:数组中重复的数据

    1、前言 2、思路 采用桶排序的思路,只不过桶排序需要开辟新数组,而题目中的原数组就是长度为 n,且数组中数字是 ...

  • 2021-05-05

    给定一个数组arr,只能对arr中的一个子数组排序,但是想让arr整体都有序返回满足这一设定的子数组中,最短的是多长

  • 每天一个算法

    [TOC] 排序 选择排序 先上代码: 对于长度为N的数组,选择排序需要大约N^2/2次比较和N次交换特点: 运行...

  • LeetCode 刷题总结(8)

    581. 最短无序连续子数组 思路 拷贝把备份排序,然后两个指针,依次从头到尾(i),从尾到头(j)比较排序前后两...

网友评论

      本文标题:需要排序的最短子数组长度

      本文链接:https://www.haomeiwen.com/subject/gfaibhtx.html