这是悦乐书的第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+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论