时间戳

首页 > 解决方案 > 在 Python 中遍历大型数组以查找缺失元素的最有效方法

python - 在 Python 中遍历大型数组以查找缺失元素的最有效方法

问题描述

我正在尝试在线测试。测试要求编写一个函数，给出一个范围为 1 到 100000 的最多 100000 个整数的列表，它将找到第一个丢失的整数。

例如，如果列表为 [1,4,5,2]，则输出应为 3。

我遍历列表如下

def find_missing(num)
    for i in range(1, 100001):
    if i not in num:
        return i

我收到的反馈是代码在处理大列表时效率不高。我很新，我找不到答案，我怎样才能更有效地迭代？

标签： pythonlistloops

解决方案

第一个改进是通过set对重复成员资格测试使用 a 来使您的线性化：

def find_missing(nums)
    s = set(nums)
    for i in range(1, 100001):
        if i not in s:
            return i

鉴于 C 优化的 python 排序是如何进行的，您还可以执行以下操作：

def find_missing(nums)
    s = sorted(set(nums))
    return next(i for i, n in enumerate(s, 1) if i != n)

但这两者在创建新集合时都相当低效。您可以通过就地排序来避免这种情况：

from itertools import groupby

def find_missing(nums):
    nums.sort()  # in-place
    return next(i for i, (k, _) in enumerate(groupby(nums), 1) if i != k)

推荐阅读