پاسخ پرسش عدد گم شده در حالت کلی O(n)
def missing_int_o_n(a):
''' Solve it with Pigeonhole principle.
There are N integers in the input. So for the
first N+1 positive integers, at least one of
they must be missing.
'''
# We only care about the first N+1 positive integers.
# occurrence[i] is for the integer i+1.
occurrence = [False] * (len(a) + 1)
for item in a:
if 1 <= item <= len(a) + 1:
occurrence[item - 1] = True
# Find out the missing minimal positive integer.
for index in range(len(a) + 1):
if not occurrence[index]:
return index + 1