查找数组最小缺失正整数的Python解法时间复杂度是多少

问题描述 #

给定包含N个整数的数组A，返回A中未出现的最小正整数（大于0）。

测试示例 #

• 输入A = [1, 3, 6, 4, 1, 2]，返回值应为5
• 输入A = [1, 2, 3]，返回值应为4
• 输入A = [-1, -3]，返回值应为1

待分析代码 #

def solution(A):
    m = max(A)
    if m < 1:
       return 1

    A = set(A)
    B = set(range(1, m + 1))
    D = B - A
    if len(D) == 0:
        return m + 1
    else:
        return min(D)

时间复杂度解答 #

各步骤耗时拆解 #

1. 求数组最大值max(A)：遍历数组所有元素，时间复杂度O(n)，n为数组长度。
2. 数组转集合set(A)：遍历数组所有元素做哈希插入，平均时间复杂度O(n)。
3. 生成1到m的集合set(range(1, m+1))：你疑惑的点这里不会达到O(nlogn)，不管输入的元素是不是有序，set插入用的是哈希表，平均单次插入开销是O(1)，这里只需要遍历m个连续整数依次插入即可，所以总开销是O(m)，m是数组的最大值。
4. 集合求差集B - A：遍历B的所有元素查询是否在A中，哈希查询平均O(1)，时间复杂度O(m)。
5. 求差集最小值min(D)：遍历D的所有元素，最坏情况D的长度为m，时间复杂度O(m)。

总复杂度结论 #

整体平均时间复杂度是O(max(n, m))：

• 如果数组的最大值m不超过n（比如数组是1到n的连续整数，或者中间缺少数值），那总复杂度就是O(n)，符合最优时间复杂度要求。
• 如果数组的最大值m远大于n（比如输入是[1, 1000000]，数组长度只有2，m是1e6），这个代码的时间复杂度会飙升到O(m)，会出现严重的性能问题甚至超时，这也是这个代码的缺陷——没有利用「最小未出现正整数一定不超过n+1」的特性做优化，没必要生成超过n的元素范围。

内容的提问来源于stack exchange，提问作者prison-mike