最短排序

[编程题]最短排序

热度指数：12570 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。

给定一个整数数组A及它的大小n，请返回最短子数组的长度。

测试样例：

[1,5,3,4,2,6,7],7

返回：4

算法知识视频讲解

Python

lx的流星

# -*- coding:utf-8 -*-

class ShortSubsequence:
    def findShortest(self, A, n):
        # write code here
        list1=A
        list1=sorted(list1)
        re=[]
        for i in range(n):
            if list1[i]!=A[i]:
                re.append(i)
        if len(re)!=0:
            return max(re)-min(re)+1
        else:
            return 0
找到与排好序的列表的不同的段，用最后的减去最前的位置加一就行了

编辑于 2019-07-22 20:35:21 回复(0)

Python

离疏

# -*- coding:utf-8 -*-
class ShortSubsequence:
    def findShortest(self, A, n):
        start, end = 0, n-1#用两个指针一个在头一个在尾
        while min(A[start + 1:]) >= A[start]:#先判断头指针与A[start+1:]的最小值比较，然后不断后移直到A[start] 比 A[start+1:]中最小的还要大就停止
            start += 1
            if start >= n-1:
                return 0
        while A[end] >= max(A[start:end]):#然后尾指针开始移动不断用A[end] 与A[start:end]中的最大值比较
            end -= 1
        return end-start+1#最后用j-i+1就是中间需要排序的大小

发表于 2018-08-24 10:37:50 回复(0)

Python

XShura

用了个骚操作，用两个指针一个在头一个在尾，先判断头指针与A[i+1:]的最小值比较，然后不断后移直到A[i] 比 A[i+1:]中最小的还要大就停止，然后尾指针开始移动不断用A[j] 与A[i:j]中的最大值比较。最后用j-i+1就是中间需要排序的大小

class ShortSubsequence:
    def findShortest(self, A, n):
        i, j = 0, n-1
        while min(A[i + 1:]) >= A[i]:
            i += 1
            if i >= n-1: return 0
        while A[j] >= max(A[i:j]):
            j -= 1
        return j-i+1

发表于 2018-08-15 21:00:48 回复(0)

Python

华科平凡

python solution,时间复杂度为排序的时间复杂度NlogN。

思路，先把数组排序得到一个排序数组，针对两个数组（排序和未排序）同时进行遍历，如果第一次遇到了某个位置不相同，那么，这个位置一定是起始位置。如果是第二次甚至是第三次……，那么这个位置就做为结束位置，遍历完，将end-start+1就得到了结果。

class ShortSubsequence:
    def findShortest(self, A, n):
        B, start, end, canEnd = sorted(A), 0, -1, False
        for i, v in enumerate(A):
            if v != B[i]:
                if not canEnd:
                    start = i
                    canEnd = True
                else:
                    end = i
        return end - start + 1

编辑于 2017-11-07 18:40:57 回复(5)