时间戳

首页 > 解决方案 > 遍历值列表时超过了执行时间

python - 遍历值列表时超过了执行时间

问题描述

我正在解决一个挑战，看看如果一个且只有一个元素从其中删除，给定序列是否严格增加。输出应该是True或False。这是我的代码：

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

它在大多数情况下都有效，但此代码存在 2 个问题：

  1. 当这些是输入时，输出是未定义[30, 60, 50, 80, 100, 200, 150]的： ,[1000, 1000, 2000, 3000, 4000, 5000, 5000]

  2. 当这是输入时，会超过执行时间： [-9996, -9995, -9994, -9993, -9991, -9989, -9987, -9986, -9985, -9983, -9982, -9980, -9978, -9977, -9976, -9975, -9974, -9972, -9968, -9966, -9965, -9961, -9957, -9956, -9955, -9954, -9952, -9948, -9942, -9939, -9938, -9936, -9935, -9932, -9931, -9927, -9925, -9923, -9922, -9921, -9920, -9919, -9918, -9908, -9905, -9902, -9901, -9900, -9899, -9897, -9896, -9894, -9888, -9886, -9880, -9878, -9877, -9876, -9874, -9872, -9871, -9870, -9869, -9868, -9867, -9865, -9857, -9856, -9855, -9854, -9853, -9852, -9851, -9849, -9848, -9846, -9845, -9843, -9842, -9841, -9840, -9837, -9834, -9828, -9826, -9824, -9823, -9820, -9816, -9814, -9812, -9811, -9810, -9809, -9807, -9806, -9804, -9803, -9801, -9800]

我的猜测是，我的代码资源密集型并不是唯一的问题，因为 #1 中的输入非常小。但是，我不知道它可能是什么。

标签： pythonexecution-time

解决方案

def strictly_increasing_but_one(sequence):
    sequence = np.array(sequence)

    # The differences should always be positive 
    # if we have a strictly increasing sequence
    differences = np.diff(sequence)
    if (differences <= 0).sum() > 1:
        # We found more than one element which is smaller 
        # than the previous element
        return False

    # However, it could be that there were elements which were 
    # greater than their predecessors but still lower than their 
    # pre-predecessors (check test4 for an example). Hence, we need to
    # remove the previously found smaller elements and check again:
    keep = np.insert(differences > 0, 0, True)
    differences = np.diff(sequence[keep])
    return (differences <= 0).sum() == 0

test1 = [30, 60, 50, 80, 100, 200, 150]
test2 = [1000, 1000, 2000, 3000, 4000, 5000, 5000]
test3 = [-9996, -9995, -9994, -9993, -9991, -9989, -9987, -9986, -9985, -9983, -9982, -9980, -9978, -9977, -9976, -9975, -9974, -9972, -9968, -9966, -9965, -9961, -9957, -9956, -9955, -9954, -9952, -9948, -9942, -9939, -9938, -9936, -9935, -9932, -9931, -9927, -9925, -9923, -9922, -9921, -9920, -9919, -9918, -9908, -9905, -9902, -9901, -9900, -9899, -9897, -9896, -9894, -9888, -9886, -9880, -9878, -9877, -9876, -9874, -9872, -9871, -9870, -9869, -9868, -9867, -9865, -9857, -9856, -9855, -9854, -9853, -9852, -9851, -9849, -9848, -9846, -9845, -9843, -9842, -9841, -9840, -9837, -9834, -9828, -9826, -9824, -9823, -9820, -9816, -9814, -9812, -9811, -9810, -9809, -9807, -9806, -9804, -9803, -9801, -9800]
test4 = [1000, 2000, 1500, 1800, 5000]

strictly_increasing_but_one(test1) # False
strictly_increasing_but_one(test2) # False
strictly_increasing_but_one(test3) # True
strictly_increasing_but_one(test4) # False

解释：假设您有一个严格递增的数字序列，那么每个元素与前一个元素之间的差应该始终为正：

for all x[i]: x[i] > x[i-1]

所有低于其先前元素的元素都会导致负差异。我们可以计算差异，numpy.diff然后检查其中有多少是负数。如果我们发现不止一个，我们知道至少有两个元素需要删除以使序列严格递增（这在 if 语句中涵盖）。

但是，仍然可能存在大于其直接前辈但低于之前的元素的元素（请参阅 参考资料test4）。因此，我们从之前删除干扰者并再次检查是否发现任何负面差异。如果我们不这样做，我们可以确定该序列现在是严格递增的。

推荐阅读