我正在嘗試在線測驗。該測驗要求撰寫一個函式，該函式給出最多 100000 個整數的串列，其范圍是 1 到 100000，將找到第一個缺失的整數。
例如，如果串列是 [1,4,5,2]，則輸出應該是 3。
我遍歷串列如下
def find_missing(num)
for i in range(1, 100001):
if i not in num:
return i
我收到的反饋是代碼在處理大串列時效率不高。我很新，我找不到答案，我怎樣才能更有效地迭代？
uj5u.com熱心網友回復：
第一個改進是通過使用 aset進行重復成員資格測驗使您的線性化：
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)
uj5u.com熱心網友回復：
您可以使用Counter來計算串列的每次出現次數。出現次數為 0 的最小數字將是您的輸出。例如：
from collections import Counter
def find_missing():
count = Counter(your_list)
keys = count.keys() #list of every element in increasing order
main_list = list(range(1:100000)) #the list of values from 1 to 100k
missing_numbers = list(set(main_list) - set(keys))
your_output = min(missing_numbers)
return your_output
uj5u.com熱心網友回復：
對于任何范圍的數字，總和由高斯公式給出：
# sum of all numbers up to and including nums[-1] minus
# sum of all numbers up to but not including nums[-1]
expected = nums[-1] * (nums[-1] 1) // 2 - nums[0] * (nums[0] - 1) // 2
如果缺少一個數字，則實際總和將為
actual = sum(nums)
不同之處在于缺少的數字：
result = expected - actual
這個計算是O(n)，它是你所能得到的最有效的。expected是一種O(1)計算，而actual實際上必須將元素相加。
一種較慢但類似復雜性的方法是使用范圍或 以鎖步方式沿著序列步進itertools.count：
for a, e in zip(nums, range(nums[0], len(nums) nums[0])):
if a != e:
return e # or break if not in a function
請注意單個比較a != e與線性包含檢查（如 ）之間的區別e in nums，后者必須平均迭代一半nums才能得到答案。
uj5u.com熱心網友回復：
這在沒有 numpy 的情況下有效：
def find_missing(a_list):
missing_list = []
a_list.sort()
minum = min(a_list)
maxnum = max(a_list)
for i in range(minum, maxnum 1):
if i not in a_list:
missing_list.append(i)
return missing_list
My_list = [4,2,1,5,6,7,8,11,10]
missingIntList = find_missing(My_list)
if missingIntList:
for num in missingIntList:
print(f"{num} is missing")
else:
print("Found them all")
您也可以使用差異（）：
def find_missing(a_lst):
start = a_lst[0]
end = a_lst[-1]
return sorted(set(range(start, end 1)).difference(a_lst))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/339426.html
上一篇：如何為串列指定索引名稱？