如何以最优化的方式找到非负整数数组中缺失的最小非负整数?

Question

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).我正在寻找一个更优化的解决方案!

Answer 1

可以在线性时间和线性空间中完成。你必须首先意识到结果受n的约束。

因此，创建一个最多包含n+1个条目的查找表(bitset就可以)，然后遍历输入数组。对于每个数字<N将表中的项翻转为1。第一个非1的值将由结果决定。根据定义，至少有一位不为1。>

Answer 2

无sort-:

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

Using Dictionary [Hashmap]-:

(平摊的)时间复杂度在字典的大小中是常数(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..!