Shortest Unsorted Continuous Subarray

Posted on | Edited on | In | | Views:

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.

给一个数组, 返回一个最短子数组, 使这个子数组排序后, 原数组是一个升序数组.

例子:

[1, 2, 3, 4, 5] => 0

因为这个数组已经是升序的

[6, 5, 4, 3, 2] => 5

因为这个数组是降序的

[2, 6, 4, 8, 10, 9, 15] => 5

因为最短的需要排序的字数组是 [6, 4, 8, 10, 9]

思路

申请一个空间, 储存排序后的原数组. 然后分别从左和从右遍历数组, 遇到的第一个与原数组不同的数, 那分别就是要返回的子数组的左右边界值.

ori =  [2, 6, 4, 8, 10, 9, 15]
sort = [2, 4, 6, 8, 9, 10, 15]
           l            r

output = r - l + 1 = 5 - 1 + 1 = 5

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shortestUnsorted(nums):
    if len(nums) <= 1:
        return 0
    left = right = -1
    sort = sorted(nums)
    if sort == nums:
        return 0
    #left to right scan
    for i in range(len(nums)):
        if nums[i] != sort[i]:
            left = i
            break

    #right to left scan
    for j in reversed(range(len(nums))):
        if nums[j] != sort[j]:
            right = j
            break

    return right - left + 1

时间复杂度

$O(nlogn)$