首页 > 试题广场 >

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

[编程题]求需要排序的最短子数组长度

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

给定一个无序数组arr。如果想要让所有元素从小到大排列，求出需要排序的最短子数组长度。例如： arr = {1，5，3，4，2，6，7} 返回4，因为只有{5，3，4，2}需要排序。注：本题请尽量做到时间复杂度O(N)，额外空间复杂度O(1)

算法知识视频讲解

推荐

马客(Mark)

为什么楼上的都要排序。。。不是要求O(n)么。。。

只要求出左边最长上升前缀且都小于右边的值，右边同理。。。

int getMinSortLength(vector<int> arr, int len) {
    if(len == 0) return 0;
        int a = 1;
        while(a < len && arr[a] >= arr[a - 1]) ++a;
        if(a == len) return 0;
        int mi = 0x7fffffff;
        for(int i = a; i < len; ++i)if(arr[i] < mi) mi = arr[i];
        while(a > 0 && arr[a - 1] > mi) --a;
        
        int b = len - 1;
        while(b > 0 && arr[b - 1] <= arr[b]) --b;
        int mx = 0x80000000;
        for(int i = 0; i < b; ++i)if(arr[i] > mx) mx = arr[i];
        while(b < len && arr[b] < mx) ++b;
        
        return b - a;
    }

编辑于 2015-03-25 20:45:09 回复(5)

Java

西瓜ღ

import java.util.*;

public class ShortSubsequence {
    public int findShortest(int[] A, int n) {
        if(n <= 1) return 0;
        int maxLeft = A[0];
        int minRight = A[n - 1];
        int start = 0;
        int end = n - 1;
        //从左到右求无序时最右的位置
        for(int i = 0; i < n; i++){
            if(A[i] >= maxLeft){
                maxLeft = A[i];
            }else{
                start = i;
            }
        }
        if(start == 0){
            return 0;
        }
        //从右到左求无序时最左的位置
        for(int i = n - 2; i >= 0; i--){
            if(A[i] <= minRight){
                minRight = A[i];
            }else{
                end = i;
            }
        }
        return start - end + 1;
    }
}

编辑于 2019-07-10 19:06:51 回复(0)