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

Question

我正在完成一项挑战，看看如果从中删除一个且仅一个元素，给定序列是否严格递增。输出应该是 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 个问题：

输出是 undefined 当这些是输入时：[30, 60, 50, 80, 100, 200, 150], [1000, 1000, 2000, 3000, 4000, 5000, 5000]
输入时超过执行时间：[-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 中的输入非常小。但是，我不知道它可能是什么。

Answer 1

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）。因此，我们从之前删除 disturbers 并再次检查我们是否发现任何负面差异。如果我们不这样做，我们可以确定序列现在是严格递增的。

Answer 2

您只需要测试 index + 1 处的值是否大于 index 处的值，这可以使用 numpy 一次性完成：

import numpy as np

# three examples
a = [30, 60, 50, 80, 100, 200, 150]
b = [1000, 1000, 2000, 3000, 4000, 5000, 5000]
c = [-9996, -9995, -9994, -9993, -9991, -9989, -9987]

for test in [a, b, c]:
    test = np.array(test)
    result = np.all(test[1:] > test[:-1])
    print(result)

给出：

False
False
True

您可以将此测试放入一个从测试序列中一次删除一个元素的函数中，以替换您的原始函数。

def test_seq(seq):
    for i in range(len(seq) - 1):
        test = np.array(seq[:i] + seq[i+1:])
        if not np.all(test[1:] > test[:-1]):
            return False
    return True

Answer 3

您可以找到给定数组的 length of longest increasing subsequence，如果该长度是 equal or one less than the total length of the array，那么答案将是 True 或者是 False。

您可以使用 DP in N-square 或 Divide and Conquer method in N log N 找到 Longest Increasing Subsequence。

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

Execution time surpassed while traversing through a list of values

python

execution-time