题目

在给定数组中找到一个最短连续子数组,当给这个子数组排序后,整个数组也有顺序了。

比如:

1
2
3
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

方法一

将0~Size(A)排序,0~L-1和R+1~Size(A)范围的数应该与原数组相同,因此从左到右不想等的位置为L,从右到左不想等的是R

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> clone_nums(nums);
sort(clone_nums.begin(), clone_nums.end());
int l = 0, r = 0;
for (int i = 0; i < clone_nums.size(); i++) {
if (clone_nums[i] != nums[i]) {
l = i;
break;
}
}
for (int i = clone_nums.size() - 1; i > 0; i--) {
if (clone_nums[i] != nums[i]) {
r = i;
break;
}
}
return r==l?0:r-l+1;
}
};

时间复杂度 O(nlgn)
空间复杂度 O(n)

方法二

这个问题主要是找到数组A左右两个边界L、R,排序L~R的元素,整个数组就有顺序了。

  • L~R的元素最小值应该大于0~L-1的最大值
  • L~R的最大值应该小于R+1~Size(A)的最小值

首先找到降序中最小和最大的两个元素l、r

  • 在最小元素l左边的元素都比它小,所以它的实际位置应该在i
  • 在最大元素r右边的元素应该都比它更大,所以它的实际位置应该在j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
if (nums.size() < 2) {
return 0;
}
int l = -1, r = -1;
for (int i = 0; i < nums.size()-1; i++) {
if (nums[i] > nums[i+1]) {
if (l==-1 || nums[i+1] < nums[l]) l = i+1; // 找到无序元素中最小的值, 它将作为子数组左边界
}
}
for (int i = nums.size() - 1; i > 0; i--) {
if (nums[i] < nums[i-1]) {
if (r==-1 || nums[i-1] > nums[r]) r=i-1; // 找到无序元素中最大的值,它将作为子数组的右边界
}
}
if (l == -1 && r == -1) return 0;
int i = 0;
while (l > i) { // 得到左边界实际位置
if (nums[l] < nums[i]) {
break;
}
i++;
}
int j = nums.size() - 1;
while (r < j) { // 得到右边界实际位置
if (nums[r] > nums[j]) {
break;
}
j--;
}
return j-i+1;
}
};

时间复杂度O(n)
空间复杂度O(1)