思路给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
站在用户的角度思考问题,与客户深入沟通,找到桐柏网站设计与桐柏网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站设计、网站制作、外贸营销网站建设、企业官网、英文网站、手机端网站、网站推广、主机域名、网络空间、企业邮箱。业务覆盖桐柏地区。请你找出符合题意的 最短 子数组,并输出它的长度。
方法一:双指针 + 排序
最终目的是让整个数组有序,那么可以先将数组拷贝一份进行排序,然后使用两个指针i
和j
分别找到左右两端第一个不同的地方,那么[i,j]
这一区间即是答案
java代码如下:
class Solution {public int findUnsortedSubarray(int[] nums) {int n = nums.length;
int[] arr = nums.clone();//java中的clone对于一维数组是深拷贝,重新分配空间,并将元素复制过去,对clone后的数组进行修改不会影响源数组。但是对二维数组是浅拷贝,复制的是引用,实际上指向的是同一个地址,对拷贝的二维数组修改或者排序都会影响原二维数组
Arrays.sort(arr);
int i = 0, j = n - 1;
while (i<= j && nums[i] == arr[i]) i++;
while (i<= j && nums[j] == arr[j]) j--;
return j - i + 1;
}
}
方法二:双指针 + 线性扫描(一次遍历)
将整个数组分成三段处理,一次遍历
正常排序(1 2 3 4 5): 左边所有元素的大值(2)<= 每个元素(例如3)<= 右边所有元素的最小值(4)
求解: 2 6 8 10 4 9 15
其中:
从左到右 9是最后一个小于 (左边所有元素大值)的
从右到左 6是最后一个大于 (右边所有元素最小值)的
故解为求:
java代码如下(算法有点晦涩难懂,建议跟着例子在纸上走一遍):
class Solution{public int findUnsortedSubarray(int[] nums) {int length = nums.length;
int leftDiff = -1;
int rightDiff = -1;
//大值是顺序遍历使用的(求需排序数组的右边边界索引rightDiff), 也可以取Integer.MIN_VALUE
int max = nums[0];
//最小值是倒序遍历使用的(求需排序数组的左边边界索引leftDiff), 也可以取Integer.MAX_VALUE
int min = nums[length - 1];
for (int i = 0; i< length; i++) {//顺序执行, 判断 当前值是否小于 已遍历的大值, 是的话属于需排序的数组元素, 替换rightDiff; 否就更新大值
if (nums[i]< max){rightDiff = i;
} else {max = nums[i];
}
//倒序执行, 判断 当前值是否大于 已遍历的最小值, 是的话属于需排序的数组元素, 替换leftDiff; 否就更新最小值
int index = length - 1 - i;
if (nums[index] >min){leftDiff = index;
} else {min = nums[index];
}
}
return leftDiff != -1 ? rightDiff - leftDiff + 1 : 0;
}
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧