Как уменьшить лимит времени выполнения для списка-обходчика - PullRequest
Новая
       14

Как уменьшить лимит времени выполнения для списка-обходчика

0 голосов
/ 17 февраля 2020

Я работаю над проблемой Python в кодовом сигнале и пытаюсь определить, является ли данный список строго возрастающей последовательностью, когда из него удален только один элемент. Итак, я построил код, который в for-l oop удаляет элемент i из списка и проверяет, является ли он возрастающей последовательностью, а затем заменяет этот элемент по этому точному индексу и начинает заново. Это код: 

def almostIncreasingSequence(sequence):

    for i in range(len(sequence)):
        element = sequence[i]
        del sequence[i]

        if all(i < j for i, j in zip(sequence, sequence[1:])):
            return True
        sequence.insert(i, element)

    return False

Код работает хорошо, но вызывает ошибку во время выполнения. Есть ли способ улучшить этот существующий код, чтобы он работал быстрее?

1 Ответ

2 голосов
/ 17 февраля 2020

Было бы быстрее пробежаться по списку, сравнивая каждое значение с предыдущим, чтобы убедиться, что оно строго увеличивается. Позвольте этому не быть верным для одного числа в списке и пропустите этот номер. К сожалению, не все так просто, как мы видим ниже:

Не сработает (например, [1,4,2,3]) 

def almostIncreasingSequence(sequence):
    lastValue = sequence[0]
    removed_value = False
    for i in range(1,len(sequence)):
        if sequence[i] <= lastValue:
            if removed_value:
                return False
            else:
                removed_value = True
        else:
            lastValue = sequence[i]
    return True

Вместо этого нам нужно охватить две возможности, если мы столкнемся с невозрастающим: удалить текущее число (например, [1,2,1,3]) или удалить предыдущее (например, [1,2,8,4] ]). У нас также есть некоторые крайние случаи для удаления первого или последнего числа в списке.

Окончательное (не очень красивое) решение 

def almostIncreasingSequence(sequence):
    lastValue = sequence[0]
    skipped_value = False
    for i in range(1,len(sequence)):
        if sequence[i] <= lastValue:
            if i+1 == len(sequence):
                return not skipped_value # last number is not decreasing, skip if we can
            if skipped_value: 
                # if we've already skipped a number - won't work
                return False
            elif sequence[i+1] > sequence[i-1]:
                # skipping the current number will fix it
                skipped_value = True
                lastValue = sequence[i-1]
            else:
                # try and skip the previous number
                skipped_value = True
                if i == 1 or sequence[i] > sequence[i-2]:
                    # can skip the previous number and it'll work
                    lastValue = sequence[i]
                else:
                    # we have no chance
                    return False  
        else:
            lastValue = sequence[i]
    return True
...