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 <=.

解法

算法复杂度 O(n)，空间复杂度 O(n)

思路

数组分成三部分：

• 有序数组
• 无序数组
• 有序数组

第一个和第三个不一定存在。如果数组是一个递增的数组，那么从 0 到某个元素的位置的最大值应该等于这个 位置的值。

例如：

[1, 2, 3, 5]

例如在 3 这个位置，其最大是 3， 在 5 这个位置最大值是 5 。我们开辟一个数组，保存每个位置当前的最大值， 如果这个最大值等于这个位置的值。从后往前遍历这个数字，如果每一个值都和当前输入位置值都相同，那么这个 元素是处于正确的位置上。

nums: [2, 6, 4, 8, 10, 9, 15]

maxs: [2, 6, 6, 8, 10, 10, 15]

当我们找到不同的值时，说明这个位置是乱序的末尾，例如上面的数组，15 等于 15， 9 不等于 10，那么 9 这个 位置是乱序的末尾。

接下来的问题是找到乱序的开端。我们从前往后遍历时，如果 maxs[i] == nums[i] 说明当前是个递增的序列。 如果出现 maxs[i] != nums[i] ，说明这个位置的元素位置不正确。此时，不正确的位置肯定在这个位置的或者 它的左侧。

• 如果位于这个位置，则说明乱序的元素都比左侧有序数组大
• 如果位于这个位置左侧，则说明乱序元素有比左侧有序数组元素还大的点

我们可以遍历这个起始位置(start)和刚才发现的位置(end)，找出最小值，然后在前面有序数组中进行二分查找， 查找这个元素的位置，这个位置就是乱序数组的开始。

代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        vector<int> maxs;
        int length = nums.size();
        maxs.reserve(length);
        int current_max = nums[0];
        for (int& num : nums) {
            if (num > current_max) {
                current_max = num;
            }
            maxs.push_back(current_max);
        }
        int i = length - 1;
        while (i >= 0) {
            if (nums[i] == maxs[i]) {
                --i;
            } else {
                break;
            }
        }
        int end = i;
        /* corner case: already sorted */
        if (i < 0) return 0;

        i = 0;
        while (i < length) {
            if (maxs[i] == nums[i]) {
                ++i;
            } else {
                break;
            }
        }
        int start = i;
        int min_in_unsorted = nums[i];
        while (i <= end) {
            if (nums[i] < min_in_unsorted) {
                min_in_unsorted = nums[i];
            }
            ++i;
        }

        start = distance(
                nums.begin(),
                upper_bound(nums.begin(), nums.begin()+start, min_in_unsorted));

        /* cout << "end = " << end << " start = " << start;
           cout << " min_in_unsorted = " << min_in_unsorted << endl; */

        return end - start + 1;
    }
};

我们使用了 STL 提供的一些函数：

• upper_bound
• distance

本文完。

• ← Previous Post
• Next Post →