欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 12:50:28
...
需要排序的最短子数组长度

题目描述

给定一个无序数组arr,求出需要排序的最短子数组的长度,对子数组排序后能使得整个数组有序,即为需要排序的数组。例如:arr=[1,5,3,4,2,6,7]返回4,因为只有[5,3,4,2]需要排序。

输入描述:

输入包含两行,第一行包括一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \leq n \leq 10^5) n(1n105)代表数组arr长度,第二行n个整数,代表数组 a r r ( − 1 0 9 ≤ a r r i ≤ 1 0 9 ) arr(-10^9 \leq arr_i \leq 10^9) arr(109arri109)

输出描述:

输出一个整数,代表需要排序的最短子数组的长度。

示例1
输入
7
1 5 3 4 2 6 7
输出
4
备注:

时间复杂度 O ( n ) O(n) O(n),额外空间复杂度 O ( 1 ) O(1) O(1)


题解:

分别记录两边需要排序元素的边界即可。具体来说就是:

  • 从左往右遍历,记录左侧出现的最大值,记为 max ,如果当前数字 a[i] < max,说明若排序,max 必然会挪到 a[i] 右边,记录最右边出现这种情况的位置;
  • 从右往左遍历,记录右侧出现的最小值,记为 min ,如果当前数字 a[i] > min, 说明若排序,min 必然会挪到 a[i] 左边,记录最左边出现这种情况的位置。

这样得到的两个坐标之间的数字就是需要排序的子数组。

代码:
#include <cstdio>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main(void) {
    scanf("%d", &n);
    int max_val = 1 << 32;
    int no_max_idx = -1;
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", a + i);
        if ( a[i] < max_val ) no_max_idx = i;
        else max_val = a[i];
    }
    if ( no_max_idx == -1 ) return 0 * puts("0");
    int min_val = a[n - 1];
    int no_min_idx = -1;
    for ( int i = n - 2; i >= 0; --i ) {
        if ( a[i] > min_val ) no_min_idx = i;
        else min_val = a[i];
    }
    return 0 * printf("%d\n", no_max_idx - no_min_idx + 1);
}