Python实现Codility最小正整数题多数测试用例失败 如何优化代码

现有代码的核心问题 #

• 没有对正整数去重：重复元素会导致索引和数值匹配错位，比如输入[1,1,2]，排序后temp为[1,1,2]，索引序列是[1,2,3]，第二个元素1≠2会误判缺失值为2，但实际正确结果是3。
• 空result调用min()会报错：如果输入的正整数是从1开始连续的序列（比如[1,2,3,4]），原有逻辑不会往result添加任何值，执行min(result)会直接抛出空序列异常。
• 排序逻辑冗余：每次往temp追加元素都执行sort，完全没有必要，只需要在所有正整数筛选完成后排序一次即可。

优化思路 #

1. 先过滤所有正整数，再去重、排序
2. 从1开始依次比对排序后的正整数，第一个不匹配的数就是答案
3. 如果所有数都匹配，答案就是最大正整数+1

优化后代码 #

def solution(A):
    # 过滤所有正整数
    positive_nums = [x for x in A if x > 0]
    # 去重后排序
    sorted_unique = sorted(set(positive_nums))
    
    expected = 1
    for num in sorted_unique:
        if num == expected:
            expected += 1
        elif num > expected:
            # 出现缺口直接返回预期值
            return expected
    # 所有正整数连续，返回下一个值
    return expected

测试验证 #

你可以用以下用例验证正确性：

• 输入[2,1,-2,5,-6] → 输出3
• 输入[1,2,3,4] → 输出5
• 输入[5,6,2,4,6] → 输出1
• 输入[1,1,2] → 输出3
• 输入[-1,-3] → 输出1
• 输入[2] → 输出1
• 输入[1] → 输出2

该方案时间复杂度为O(n log n)，完全满足Codility的性能要求，覆盖所有边界场景。

内容的提问来源于stack exchange，提问作者Christian Cruz