如何确定是否有可能获得严格递增序列？

Question

我需要确定一个函数，对于给定的整数序列（作为数组），它可以确定是否可以通过从数组中移除不超过一个元素来获得严格递增的序列。在

阵列可以在范围内

2 ≤ sequence.length ≤ 10^5, -10^5 ≤ sequence[i] ≤ 10^5

例如：

[1, 3, 2, 1]我们不能为了得到递增序列而删除任何一个数字，因此函数应该返回False。对[0, -2, 5, 6]，[1, 1]，[1, 3, 2]为真。在

我想写一个函数，从列表中删除一个数字，并检查序列是否在增加。如果对于所有迭代，我们变成False，那么函数应该返回False。在

def almostIncreasingSequence(sequence):
    def order(A):
        n = len(A)
        for i in range(n):
           if A[i] >= A[i+1]:
              result = True
        else:
              result = False            
    for i in range(len(s0)-1):
        s_i = list(sequence)
        s_i.remove(s_i.index(s_i[i]))
           if order(s_i) == True:
    return True

但我有个错误：

ValueError: list.remove(x): x not in list

原因是什么？如何完成代码？在

Answer 1

def almostIncreasingSequence(sequence):
    for i in range(len(sequence)-1):
        s_i = list(sequence)

        # Remove the item by index
        del s_i[i]

        if order(s_i) == True:
            return True

    # Need to return false at the end if we never find a solution
    return False

# You should have tested this function separately first.
# It did not work, so obviously almostIncreasingSequence wouldn't work.
def order(A):
    n = len(A)

    # Should have been n-1, not n, because you compare against n+1
    # which doesn't exist when you hit the tail
    for i in range(n - 1):
        if A[i] > A[i + 1]:
            # Need to actually return the value, not just set it to a variable
            return False
    # Only tell us it's in order if ALL the values don't fail
    return True

print almostIncreasingSequence([1, 3, 2])

Answer 2

如注释中所述，您可以使用numpy.diff来完成此操作，从而避免了检查从列表中移除1个元素的每个组合的需要

import numpy

def almostIncreasingSequence(sequence):
    diff = numpy.diff(sequence) < 1
    return diff.sum() < 2

在这里，我们首先得到相邻元素之间的差异，然后我们询问这些差异在哪里小于1并进行计数，然后根据数量得到答案。在

没有numpy，我们可以使用类似的技术

^{pr2}$

这个版本的优点是使用的内存比numpy版本少

这里有一些测试

assert almostIncreasingSequence([0, -2, 5,  6])
assert almostIncreasingSequence([1,1])
assert almostIncreasingSequence([1,3,2])
assert almostIncreasingSequence([1,2,3,0])
assert almostIncreasingSequence([1,2,3,0,10])
assert almostIncreasingSequence([10,1,2,3,4])
assert almostIncreasingSequence([1,10,2,3,4])
assert not almostIncreasingSequence([1,2,3,0,0])
assert not almostIncreasingSequence([1,2,0,3,0,10])
assert not almostIncreasingSequence([1,2,0,3,10,0])
assert not almostIncreasingSequence([1,2,3,0,10,0])
assert not almostIncreasingSequence([10,1,2,3,10,0])
assert not almostIncreasingSequence([1, 3, 2, 1])

针对评论，这里有一个早期停止版本

def almostIncreasingSequence(sequence):
    diff = 0
    for a,b in pairwise(sequence):
        if a>=b:
            diff += 1
            if diff >= 2:
                return False
    return diff < 2

还有一个附带的测试

assert not almostIncreasingSequence(itertools.chain([1, 3, 2, 1],range(10**100))) # use xrange with python 2

其他版本都需要很长时间