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

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

题目描述

给定一个无序数组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(1≤n≤105)代表数组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(−109≤arri​≤109)。

输出描述：

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

示例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);
}