如何以最优的方式从非负整数数组中找到缺失的最小非负整数？
如何以最优的方式从非负整数数组中找到缺失的最小非负整数？
提问于 2022-11-23 05:33:59
MEX (最小除外)是集合/列表中排除的最小非负整数。例：
MEX [] = 0
MEX [1,2,3,4,5,10,10000] = 0
MEX [0,1,2,3,4,5,6] = 7
MEX [0,1,3,4,1000] = 2
MEX [0,2,3,4,5,6] =1给定一个非负整数的列表，找到列表的MEX。
因此，我尝试对数组进行排序，然后将每个位置的数字与其索引进行比较，以找到丢失的最小数目。该方法的时间复杂度为O(nlogn + n)。我正在寻找一个更优化的解决方案！
回答 2
Stack Overflow用户
发布于 2022-11-23 06:02:16
它可以在线性时间和线性空间进行。你必须首先意识到结果受n的约束。
因此，最多使用n+1条目创建一个查找表(比特集可以)，然后对输入数组进行迭代。对于每个数字
Stack Overflow用户
发布于 2022-11-23 06:42:34
没有排序-：
lis=set([0,0,2,3,1,8,4,34,12,99,100])
for i in range(0,max(lis)+2):
if i not in lis:
print(i)
break使用Dictionary：
(摊销的)时间复杂度是字典大小中的常数(O(1))
lis=set([0,2,3,1,8,4,99,100])
dic={}
#for i in lis:
# dic[i]=dic.get(i,0)+1
dic=dict.fromkeys(lis, 1) # one-liner to initialize by @_aneroid
for i in range(max(lis)+1):
if i not in dic:
print(i)
break更新解决方案：-
def solution(list_1):
if not list_1:
return 0
#Condition for all elements present
# Sum of natural numbers n*(n+1)//2 -: whole number (n-1)*n//2
n=len(list_1)-1
if sum(list_1)==(n*(n+1))//2:
return max(list_1)+1
dic=dict.fromkeys(list_1, 1)
for num in range(max(list_1)+1):
if num not in dic:
return num
break
print(solution([]))
print(solution([0,1,2,3]))
print(solution([1,2,54,32,21,46,32,0,29,88]))
print(solution(list(map(int,input().split())))) # If user want to input输出：-
0
4
3
as user defined list..!页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/74542189
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号