首页 > 试题广场 >

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

[编程题]需要排序的最短子数组长度
  • 热度指数：2810 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个无序数组arr，求出需要排序的最短子数组的长度，对子数组排序后能使得整个数组有序，即为需要排序的数组。例如：arr=[1,5,3,4,2,6,7]返回4，因为只有[5,3,4,2]需要排序。

输入描述:
输入包含两行，第一行包括一个整数n，代表数组arr长度，第二行n个整数，代表数组arr。


输出描述:
输出一个整数，代表需要排序的最短子数组的长度。
示例1

输入

7
1 5 3 4 2 6 7

输出

4

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
wywzxxz头像 wywzxxz
其实类似脑筋急转弯。为了容易理解，我们从O(nlogn)出发来推导O(n)方案
方案一:O(nlogn)方案
把整个序列重新排序一下。显然的，只有挪窝的数字才需要排序。
1 5 3 4 2 6 7
1 2 3 4 5 6 7
由于只能连续子数组一同排序，所以答案是以最左、左右需要挪窝数字为左右端点的数组。

方案二：O(n)
方案一有一个问题，就是我们引入了排序却没有用到相对次序，这可能会浪费了算力。
那么有没有办法避免排序呢？
有的，对于第i个元素，如果它满足下列公式，那么它显然不必要挪窝嘛。

max(arr[0..i)<=arr[i]<=max(arr[i..n])
换过来说，如果需要挪窝，那么显然不满足这个条件不是？
so，两个for解决 

n=int(input())
if n==0:
    print(0)
else:
    arr=[int(i) for i in input().strip().split()]
    mx=arr[0];r=0;
    for i in range(len(arr)):
        mx=max(mx,arr[i])
        if mx>arr[i]:
            r=i;
    mx=arr[-1];l=len(arr)-1;
    for i in reversed(range(len(arr))):
        mx=min(mx,arr[i])
        if mx<arr[i]:
            l=i;
    print(max(0,r-l+1))




发表于 2021-05-24 16:53:27 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, l=-1, r=-1, Max=INT_MIN, Min=INT_MAX;
    scanf("%d", &n);
    int a[n];
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
        if(a[i] >= Max)
            Max = a[i];
        else
            r = i;
    }
    if(r == -1){
        puts("0");
        return 0;
    }
    for(int i=n-1;i>=0;i--){
        if(a[i] <= Min)
            Min = a[i];
        else
            l = i;
    }
    if(l == -1)
        puts("0");
    else
        printf("%d\n", r-l+1);
    return 0;
}

发表于 2020-06-02 08:24:38 回复(0)
Java
Mono_Chrome头像 Mono_Chrome

Java

题目的测试用例的目标是非递减排序的。

import java.util.Scanner;

public class Main {

    public static int getLength(int[] arr) {
        int noMinIndex = -1;
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                noMinIndex = i;
            } else {
                min = arr[i];
            }
        }

        if (noMinIndex == - 1) {
            return 0;
        }

        int noMaxIndex = -1;
        int max = arr[arr.length - 1];
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > max) {
                noMaxIndex = i;
            } else {
                max = arr[i];
            }
        }

        return noMinIndex - noMaxIndex + 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(getLength(arr));
    }
}
发表于 2019-10-08 19:15:00 回复(0)
Python
牛客657928900号头像 牛客657928900号 
lens = int(input())
nums = input()
nums = [int(i) for i in nums.split()]


def fus(nums):
    diff = [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]
    return len(diff) and max(diff) - min(diff) + 1


print(fus(nums))
编辑于 2022-03-16 20:31:41 回复(0)
致·爱丽丝头像 致·爱丽丝 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> vec(n,0);
    for (int i = 0 ; i < n; i ++) {
        int tmp ;
        cin >> tmp;
        vec[i] = tmp;
    }
    //从右向左： 找最小值，并且记录 比最小值大的 值得位置 --》 确定左边界
    // 从右向左： 找最大值， 并记录 比最大值，小的位置 --》 记录有边界
    
    int min_index = -1;//left
    int max_index = -1;//right
    int min_val = vec.back();
    int max_val = vec[0];
    for (int i = vec.size() - 2; i >= 0 ; i --) {
        if (vec[i] < min_val) {
            min_val = vec[i];
        }
        if (vec[i] > min_val) {
            min_index = i;
        }
        
    }
    for (int i = 1; i < vec.size(); i ++) {
        if (vec[i] > max_val) {
            max_val = vec[i];
        }
        if (vec[i] < max_val) {
            max_index = i;
        }
    }
    cout << max_index - min_index + 1 ;
    return 0;
}

发表于 2022-07-17 19:55:35 回复(0)
咸鱼翻身啦~头像 咸鱼翻身啦~
我的代码思想和一楼差不多，为什么只能过75%？请大佬点评！
import java.util.Scanner;
import java.util.*;
public class Main{
    public static int Minlength(int[] arr){
          if(arr.length == 0 || arr.length < 2) return 0;
          int noMinIndex = -1, noMaxIndex = -1, len, max, min;
          len = arr.length;
          min = arr[len-1];
          max = arr[0];
          for(int i = len-2; i>=0;i--){
              if(arr[i] < min){
                  min = Math.min(arr[i],min);
              }else{
                  noMinIndex = i;
              }
          }
        if(noMinIndex == -1) return 0;
        for(int i = 1; i<len; i++){
            if(arr[i] > max){
                max = Math.max(arr[i], max);
            }else{
                noMaxIndex = i;
            }
        }
        return noMaxIndex - noMinIndex + 1;
    }
    public static void main(String[] args) {
           Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i<n; i++)
            arr[i] = sc.nextInt();
        System.out.println(Minlength(arr));
    }
}
发表于 2021-05-19 21:43:01 回复(0)
C/C++
牛客91950395号头像 牛客91950395号 
#include<stdio.h>
#include<malloc.h>

int find_sort1(int *a, int n)
{
	int max = a[0], min = a[n - 1], p1 = -1, p2 = -1;
	for(int i = 0, j = n - 1; i < n, j >= 0; i++, j--)
	{
		if(a[i] >= max)
			max = a[i];
		else
			p2 = i;	
		if(a[j] <= min)
			min = a[j];
		else
			p1 = j;				
	}
	if(p1 == -1 && p2 == -1)
		return 0;
	else	
		return p2 - p1 + 1;
}

int find_sort2(int *a, int n)
{
	int max = a[n - 1], min = a[0], p1 = -1, p2 = -1;
	for(int i = 0, j = n - 1; i < n, j >= 0; i++, j--)
	{
		if(a[i] <= min)
		 min = a[i];
		else  
			p2 = i;
		if(a[j] >= max)
			max = a[j];
		else
			p1 = j;		
	}
	if(p1 == -1 && p2 == -1)
		return 0;
	else	
		return p2 - p1 + 1;
 } 
int main()
{
	int  n, i;
	scanf("%d", &n);
	int *a = (int*)malloc(sizeof(int) * n);
	for(int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	if(find_sort2(a, n) > find_sort1(a, n))
		printf("%d\n", find_sort1(a, n));
	else
		printf("%d\n", find_sort2(a, n));
	free(a);
	
	return 0;
}


编辑于 2021-03-16 21:19:48 回复(0)
Java
眼睛想旅行121头像 眼睛想旅行121 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int len=sc.nextInt();
        int[] arr=new int[len];
        for(int i=0;i<len;i++){
            arr[i]=sc.nextInt();
        }
        int sum=getMinLength(arr);
        System.out.print(sum);
    }
    public static int getMinLength(int[] arr){
        if(arr==null||arr.length<2){
            return 0;
        }
        int min=arr[arr.length-1];
        int noMinIndex=-1;
        for(int i=arr.length-2;i!=-1;i--){
            if(arr[i]>min){
                noMinIndex=i;
            }else{
                min=Math.min(min,arr[i]);
            }
        }
        if(noMinIndex==-1){
            return 0;
        }
        int max=0;
        int noMaxIndex=-1;
        for(int i=1;i!=arr.length;i++){
            if(arr[i]<max){
                noMaxIndex=i;
            }else{
                max=Math.max(max,arr[i]);
        }
    }
        return noMaxIndex-noMinIndex+1;
    }
}

发表于 2021-03-11 15:23:52 回复(0)
剑指offerorz头像 剑指offerorz

#include<iostream>

#include<vector>

using namespace std;

class Subsequence {

public:

    int shortestSubsequence(vector<int> A, int n) 

    {

        int max=A[0],min=A[n-1],i,rd1,rd2;

        for(i=1,rd1=0;i<n;i++)

        {

            if(A[i]>=max)

                max=A[i];

            else

                rd1=i;

        }

        for(i=n-2,rd2=n-1;i>=0;i--)

        {

            if(A[i]<=min)

                min=A[i];

            else

                rd2=i;

        }

        if(!rd1)

            return 0;

        else

            return rd1-rd2+1;

    }

};

int main()

{

    int a[6]={1,4,6,5,9,10};

    vector<int> b(a,a+6);

    Subsequence c;

    int d=c.shortestSubsequence(b,6);

    cout<<d<<endl;

    return 0;

}

发表于 2020-03-17 19:18:16 回复(0)
我要收offer头像 我要收offer 
// ……读取数组
        // 参考冒泡排序
        int min = arr[n-1];
        int l = -1;// 这样设置初值可以包括原数组是排好序的情况
        for(int i=n-1; i>=0;i--){// 只做一轮冒泡排序，不过并不去真的修改数组
            if(min < arr[i]){
                l = i;
            }else{
                min = arr[i];
            }
        }
        // 和上面类似
        int max = arr[0];
        int r = -1;
        for(int i = 0;i<n;i++){
            if(max > arr[i]){
                r = i;
            }else{
                max = arr[i];
            }
        }
        System.out.println(r-l+1);

发表于 2020-03-09 12:58:47 回复(0)
AnnaSophia_Robb头像 AnnaSophia_Robb 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int len; scanf("%d", &len);
    vector<int> arr(len);
    for(int i=0; i<len; i++) scanf("%d", &arr[i]);
    int maxL = arr[0];
    int cur = 1;
    int r = 0;
    while(cur < len){
        if(arr[cur] < maxL){
            r = cur;
        }
        maxL = max(maxL, arr[cur]);
        cur++;
    }
    int minR = arr[len-1];
    int l = len-1;
    cur = len-2;
    while(cur >= 0){
        if(arr[cur] > minR){
            l = cur;
        }
        minR = min(minR, arr[cur]);
        cur--;
    }
    printf("%d", r-l+1);
    return 0;
}

发表于 2020-02-09 18:48:38 回复(1)
提交观点

问题信息

排序
上传者：小小
难度：
11条回答 4907浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号