هک‌ها و تشعشعات وجدان آزاد

نوشته‌های سیدمحمدمسعود صدرنژاد

ابزار کاربر

ابزار سایت


courseware:python_programming:resources:answer:8-1

پاسخ پرسش عدد گم شده در حالت کلی 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
 
courseware/python_programming/resources/answer/8-1.txt · آخرین ویرایش: 2020/09/15 15:46 (ویرایش خارجی)