如何减少列表遍历器的执行时间限制

Question

我正在处理有关代码信号的 Python 问题，我试图查看给定列表在仅从中删除一个元素时是否为严格递增序列。所以我构建了代码，在 for 循环中，从列表中删除元素 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

代码运行良好，但会导致执行时间出错。有什么方法可以改进现有代码，使其运行得更快？

Answer 1

运行浏览列表会更快，将每个值与前一个值进行比较以确保它严格递增。允许列表中的一个数字不成立并跳过该数字。不幸的是，它并不是那么简单，如下所示：

将不起作用（例如 [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

如何减少列表遍历器的执行时间限制

How to decrease execution time limit for a list-traverser

python

list

execution-time