Action unknown: backlinkmenuitem

پاسخ پرسش عدد گم شده در حالت کلی 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