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

例如:
[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))
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 一、排序简介 我们通常所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。 排序算法大体可分为两种:...
    小碧小琳阅读 3,770评论 0 1
  • 最近在看数据结构,研究了一下常用的几种排序方法:1.冒泡排序,2.选择排序,3.插入排序,4.希尔排序,5.快速排...
    wo883721阅读 5,348评论 0 4
  • 目录 1. 栈和队列1.用两个队列实现栈2.用两个栈实现队列3.实现一个栈,可以用常数级时间找出栈中的最小值4.判...
    MigrationUK阅读 8,162评论 4 20
  • 今天下课后,老师教给我们一个游戏,游戏的名字是跳房子。这个游戏可好玩了,用沙包投到哪里就跳到哪里,小朋友...
    6f9d6340d564阅读 761评论 0 0
  • 五月二十九日,天晴。雨后的太平峪内,空气中的湿度是很大的。人走在毒辣辣的太阳下,裸露的皮肤被晒得烧疼烧疼的。这一天...
    邓文伟阅读 3,280评论 0 0

友情链接更多精彩内容