最短无序连续子数组
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 17.4 MB
/*
* 思路:
* 我们可以使用Java Stream API来简化代码。
* 首先将数组转换为Stream,并排序。然后将排序后的Stream转换回数组。
* 接下来,使用IntStream找到第一个和最后一个不相等的元素的索引。
* 最后计算需要排序的子数组长度。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] sorted = Arrays.stream(nums).sorted().toArray();
int left = IntStream.range(0, nums.length).filter(i -> nums[i] != sorted[i]).findFirst().orElse(-1);
int right = IntStream.range(0, nums.length).map(i -> nums.length - 1 - i).filter(i -> nums[i] != sorted[i]).findFirst().orElse(-1);
return (left == -1) ? 0 : right - left + 1;
}
}
解释
方法:
该题解的思路是先找到最短无序连续子数组的候选区间 [l, r],然后再扩展该区间直到满足条件。具体步骤如下:
1. 从左到右扫描数组,找到第一个破坏升序的位置 l;
2. 从右到左扫描数组,找到最后一个破坏升序的位置 r;
3. 如果没找到 l 和 r,说明数组本身有序,直接返回 0;
4. 在 [l, r] 区间内找到最小值 Min 和最大值 Max;
5. 从 l 开始向左扩展,直到找到第一个小于 Min 的位置,更新 l;
6. 从 r 开始向右扩展,直到找到第一个大于 Max 的位置,更新 r;
7. 返回 r - l + 1 作为最短无序连续子数组的长度。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在第一步寻找破坏升序的位置时,为什么选择从左到右扫描数组,这种方法有没有考虑到所有可能的破坏升序的情况?
▷🦆
第二步从右到左扫描以寻找最后一个破坏升序的位置,这一步的逻辑是怎样的?即为什么要从数组的末尾开始扫描?
▷🦆
在扩展区间 [l, r] 时,扩展的标准是基于什么?即为何要找到小于最小值 Min 和大于最大值 Max 的位置?
▷🦆
如果数组中存在多个局部最小或最大值,这种方法能够准确地确定最短无序连续子数组的起始和结束位置吗?
▷