一 题目:
二 思路:
分析:这个子数组有个特征
- 子数组前面的数都是升序的,且最后一个数小于子数组里的任意一个数
- 子数组后面的数都是升序的,且第一个数大于子数组里的任意一个数
因此可以分析出几个思路:
思路1:双指针+排序
- 我们可以先拷贝个数组对其排序
- 然后从左到右进行比较,第一个不同的点即为子数组起点
- 然后从右到左进行比较,第一个不同的点即为子数组终点
时间复杂度:O(nlogn),空间复杂度:O(n)
思路2:效率更高
同时从前往后和从后往前遍历,分别得到要排序数组的右边界和左边界;
- 寻找右边界:
从前往后遍历的过程中,用max记录遍历过的最大值,如果max大于当前的nums[i],说明nums[i]的位置不正确,属于需要排序的数组,因此将右边界更新为i,然后更新max;这样最终可以找到需要排序的数组的右边界,右边界之后的元素都大于max; - 寻找左边界:
从后往前遍历的过程中,用min记录遍历过的最小值,如果min小于当前的nums[j],说明nums[j]的位置不正确,应该属于需要排序的数组,因此将左边界更新为j,然后更新min;这样最终可以找到需要排序的数组的左边界,左边界之前的元素都小于min;
(从前往后遍历和从后往前遍历两个过程可以分两次循环完成,也可以放一起完成,这样的话就有:j=len-i-1)
时间复杂度:O(n) ,空间复杂度:O(1)
三 代码:
思路1,双指针+排序
class Solution {
public int findUnsortedSubarray(int[] nums) {
//拷贝份
int[] clone = nums.clone();
Arrays.sort(clone);
//子数组左边界
int left=0;
//子数组右边届
int right=nums.length-1;
while (left<nums.length){
if (nums[left]==clone[left]){
left++;
}else {
break;
}
}
while (right>=0){
if (nums[right]==clone[right]){
right--;
}else {
break;
}
}
return right>left?right-left+1:0;
}
}
思路2:
public int findUnsortedSubarray(int[] nums) {
int len=nums.length;
int max=nums[0];
int min=nums[len-1];
//这里right定义为-1,是为了避免数组本身有序的情况
int left=0,right=-1;
for (int i = 0; i < len; i++) {
//寻找右边届
if (max>nums[i]){
right=i;
}else {
max=nums[i];
}
//寻找左边界
if (min<nums[len-1-i]){
left=len-1-i;
}else {
min=nums[len-1-i];
}
}
return right-left+1;
}
网友评论