关于算法:每日一题需要排序的最短子数组长度

189次阅读

共计 722 个字符，预计需要花费 2 分钟才能阅读完成。

给定一个无序数组 arr，求出须要排序的最短子数组长度。

【例如】arr=【1,5,3,4,2,6,7】返回 4，因为只有【5,3,4,2】须要排序。

剖析：

从右向左遍历是降序的过程，用 min 记录 i 右侧的最小值。如果 arr[i] > min（此处乱序），阐明 min 的值须要放到 arr[i] 右边，用 index 记录 i 地位。找到最右边乱序的地位记录为：no_min_index
从左向右遍历是升序的过程，用 max 记录 i 左侧的最大值。如果 arr[i] < max（此处乱序），阐明 max 的值须要放到 arr[i] 左边，用 index 记录 i 地位。找到最左边乱序的地位记录为：no_max_index
最终后果：no_max_index – no_max_index + 1。最左边开始乱序的地位 – 最左边开始乱序的地位 + 1 就是最小乱序子数组的长度。

工夫复杂度：O(N)

空间复杂度：O(1)

def get_min_len(arr):
    if not arr: return 0
    min_value = arr[-1]
    no_min_index = -1
    for i in range(len(arr) - 2, -1, -1):
        if arr[i] > min_value:
            no_min_index = i
        else:
            min_value = min(min_value, arr[i])

    if no_min_index == -1: return 0

    max_value = arr[0]
    no_max_index = -1
    for i in range(1, len(arr)):
        if arr[i] < max_value:
            no_max_index = i
        else:
            max_value = max(max_value, arr[i])

    return no_max_index - no_min_index + 1

正文完