为了账号安全,请及时绑定邮箱和手机立即绑定

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

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

慕桂英4014372 2022-08-02 10:38:45
我正在处理Code Signal上的Python问题,我试图查看给定的列表是否在仅从中删除一个元素时是严格递增的序列。因此,我构建了一些代码,在 for 循环中,从列表中删除元素并检查它是否是递增序列,然后在该确切索引处替换该元素并重新开始。这是代码:idef 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 回答

?
守着一只汪

TA贡献1872条经验 获得超3个赞

浏览列表会更快,将每个值与前一个值进行比较,以确保它严格增加。对于列表中的一个数字,允许此错误,并跳过此数字。不幸的是,这并不是那么简单,正如我们在下面看到的那样:


不起作用(例如。[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


查看完整回答
反对 回复 2022-08-02
  • 1 回答
  • 0 关注
  • 89 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
微信客服

购课补贴
联系客服咨询优惠详情

帮助反馈 APP下载

慕课网APP
您的移动学习伙伴

公众号

扫描二维码
关注慕课网微信公众号