这是悦乐书的第 267 次更新, 第 281 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 134 题(顺位题号是 581). 给定一个整数数组, 找到一个连续的子数组, 按升序对该子数组进行排序, 使得整个数组也按升序排序. 找到最短的无序连续子数组并输出其长度. 例如:
输入:[2,6,4,8,10,9,15]
输出: 5
说明: 按升序对 [6,4,8,10,9] 子数组进行排序, 以使整个数组按升序排序.
注意:
数组的长度在 [1,100] 范围内.
数组可能包含重复项, 因此这里的升序表示<=.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
特殊情况: 数组第一个元素大于数组最后一个元素, 直接返回整个数组的长度即可.
正常情况: 使用两层 for 循环, 外层循环每次获取到一个元素, 内层循环就从其后面一位开始, 往后比较, 如果当前元素比后面的元素大, 将其索引记录下来, 如果后面遇到了更大的元素, 就将索引更新为较大的索引, 此索引将作为结束位置索引.
而外层循环用来参与比较的当前元素, 在当前元素比后面的元素大时, 保留当前元素的索引, 如果后面继续出现, 就取其中较小的, 此索引将作为开始位置索引. 最后, 如果结束位置的索引值大于开始位置的索引值, 就两者相减并加 1, 反之返回 0, 表示数组有序.
此解法的时间复杂度是 O(n^2), 空间复杂度是 O(1).
- public int findUnsortedSubarray(int[] nums) {
- if (nums[0]> nums[nums.length-1]) {
- return nums.length;
- }
- int start = 0, end = nums.length;
- for (int i=0; i<nums.length-1; i++) {
- for (int j=i+1; j<nums.length; j++) {
- if (nums[i]> nums[j]) {
- start = Math.max(start, j);
- end = Math.min(end, i);
- }
- }
- }
- return start - end> 0 ? start - end + 1 : 0;
- }
03 第二种解法
特殊情况: 数组第一个元素大于数组最后一个元素, 直接返回整个数组的长度即可.
正常情况: 将数组复制一份出来, 然后对复制的数组进行排序, 再和原数组进行比较, 从头和尾分别循环比较, 最后找到起始索引, 做减法再加 1, 就是最短无序连续子数组的长度.
此解法的时间复杂度是 O(n log(n)), 空间复杂度是 O(n).
- public int findUnsortedSubarray2(int[] nums) {
- if (nums[0]> nums[nums.length-1]) {
- return nums.length;
- }
- int[] temp = nums.clone();
- Arrays.sort(temp);
- int start = 0, end = nums.length-1;
- while (start <nums.length && nums[start] == temp[start]) {
- start++;
- }
- while (end> start && nums[end] == temp[end]) {
- end--;
- }
- return end - start + 1;
- }
04 第三种解法
定义数组的最大值为数组第一个元素, 最小值为倒数第一个元素, 从数组第二个元素开始, 每次拿当前元素与最大值比较, 取较大的一个, 拿最小值与倒数第二个 (从后往前递增) 元素比较取较小的一个, 如果最大值大于当前元素, 就把当前元素的索引赋值给 end, 如果最小值小于倒数第二个 (从后往前递增) 元素, 就把倒数第二个 (从后往前) 元素的索引值赋值给 start, 最后做减法再加 1, 要是数组是有序的, 最后返回的是 0, 所以 end 的初始值为 - 2,start 的初始值为 - 1.
次解法的时间复杂度是 O(n), 空间复杂度是 O(1).
- public int findUnsortedSubarray3(int[] nums) {
- if (nums[0]> nums[nums.length-1]) {
- return nums.length;
- }
- int n = nums.length, start = -1, end = -2;
- int min = nums[n - 1], max = nums[0];
- for (int i = 1; i <n; ++i) {
- max = Math.max(max, nums[i]);
- min = Math.min(min, nums[n - 1 - i]);
- if (max> nums[i]) {
- end = i;
- }
- if (min < nums[n - 1 - i]) {
- start = n - 1 - i;
- }
- }
- return end - start + 1;
- }
05 小结
算法专题目前已日更超过四个月, 算法题文章 134 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/31edd2668f2d