581. Shortest Unsorted Continuous Subarray

发表于 | 分类于

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
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.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

解法1：O(NlogN)

这题的思路是从一个sorted过的array出发，然后再用两个指针从两端往里面找和sorted之后的结果不一样的位置。
Java

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
public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        // two pointers from left and from right
        int len = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == sorted[i]) {
                len++;
            } else {
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] == sorted[i]) {
                len++;
            } else {
                break;
            }
        }
        return Math.max(0, nums.length - len);
    }
}

解法2：O(N)

这个解法是从discuss里看来的，照搬他的解释：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
It turns out that the two boundary indices i and j can be found in linear time, if we take advantage of the following three properties:
nums[0, i - 1] and nums[j + 1, n - 1] are both sorted.
nums[i] != nums_sorted[i] and nums[j] != nums_sorted[j].
nums[i - 1] <= min and max <= nums[j + 1], where min and max are the minimum and maximum values of subarray nums[i, j].
The first and third properties guarantee that the subarray nums[0, i - 1] will be exactly the same as subarray nums_sorted[0, i - 1], and the subarray nums[j + 1, n - 1] exactly the same as nums_sorted[j + 1, n - 1], while the second property ensures that i will be the first index at which the two elements of nums and nums_sorted are different and j be the last such index.
Since we aim at the shortest subarrays, from the first property alone, we need to find the two longest sorted subarrays starting at index 0 and ending at index n - 1, respectively. Assume the two subarrays are nums[0, l] and nums[r, n - 1]. If there is overlapping between these two subarrays, i.e.l >= r, then the whole array is sorted so 0 will be returned. Otherwise, the input array is not sorted. However, we cannot say sorting nums[l, r] will leave the whole array sorted, because at this moment the third property may not be satisfied.
To guarantee the third property, assume min and max are the minimum and maximum values of subarray nums[l, r], then we need to decrease l as long as nums[l] > min, and increase r as long as nums[r] < max. After this is done, it can be shown that the second property will be met automatically, and nums[l + 1, r - 1] will be the shortest subarray we are looking for (that is, i = l + 1 and j = r - 1).
Finding the longest subarrays and the maximum and minimum values of the middle subarray takes one-pass. Ensuring the third property requires a second pass. Therefore we have this two-pass solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findUnsortedSubarray(int[] nums) {
    int l = 0, r = nums.length - 1, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    while (l < r && nums[l] <= nums[l + 1]) l++;
    if (l >= r) return 0;
    while (nums[r] >= nums[r - 1]) r--;
    for (int k = l; k <= r; k++) {
        max = Math.max(max, nums[k]);
        min = Math.min(min, nums[k]);
    }
    while (l >= 0 && min < nums[l]) l--;
    while (r < nums.length && nums[r] < max) r++;
    return (r - l - 1);
}