c# - 检查整数序列是否正在增加

Question

我只是部分地通过以下问题。

给定一个整数序列，请检查是否有可能通过删除不超过一个的元素来获得严格递增的序列。

例子

sequence = [1, 3, 2, 1]
almostIncreasingSequence(sequence) = false

sequence = [1, 3, 2]
almostIncreasingSequence(sequence) = true

我的代码仅传递了一些示例:

bool almostIncreasingSequence(int[] sequence) {
   int seqIncreasing = 0;
    if (sequence.Length == 1) return true;
    for (int i = 0;i < sequence.Length-2;i++)
    {
        if ((sequence[i] == sequence[++i]+1)||(sequence[i] == sequence[++i])) 
        {
            seqIncreasing++; 
        } 
    } 
    return ((seqIncreasing == sequence.Length) || (--seqIncreasing == sequence.Length));
}

失败的例子:

Input:
    sequence: [1, 3, 2]
Output:
    false
Expected Output:
    true

Input:
    sequence: [10, 1, 2, 3, 4, 5]
Output:
    false
Expected Output:
    true

Input:
    sequence: [0, -2, 5, 6]
Output:
    false
Expected Output:
    true

Input:
    sequence: [1, 1]
Output:
    false
Expected Output:
    true

Answer 1

基于LINQ的答案很好，并且很好地表达了基本问题。易于阅读和理解，可以直接解决问题。但是，它确实存在一个问题，即它需要为原始元素中的每个元素生成一个新序列。随着序列变得更长，这将变得更加昂贵，并最终变得棘手。

它需要使用Skip()和Take()，这无济于事，它们本身增加了处理原始序列的开销。

另一种方法是扫描序列一次，但要跟踪是否已尝试删除，以及在发现不符合序列的元素时，跟踪a)如果发现删除则立即返回false，b)不要这样做。在确定序列时将删除的元素包括在内。

您尝试的代码几乎完成了此任务。这是一个有效的版本:

static bool almostIncreasingSequence(int[] sequence)
{
    bool foundOne = false;

    for (int i = -1, j = 0, k = 1; k < sequence.Length; k++)
    {
        bool deleteCurrent = false;

        if (sequence[j] >= sequence[k])
        {
            if (foundOne)
            {
                return false;
            }
            foundOne = true;

            if (k > 1 && sequence[i] >= sequence[k])
            {
                deleteCurrent = true;
            }
        }

        if (!foundOne)
        {
            i = j;
        }

        if (!deleteCurrent)
        {
            j = k;
        }
    }

    return true;
}

注意:我本来以为您的尝试可以通过较小的更改来解决。但最终，事实证明，它必须与我编写的通用实现基本相同(尤其是一旦我也修复了该实现……，请参见下文)。唯一的实质区别实际上是使用数组还是通用 IEnumerable<T>。

对于咧嘴笑，我写了另一种方法，它与基于LINQ的解决方案息息相关，因为它适用于任何序列，而不仅仅是数组。我也使它通用(尽管该类型实现了 IComparable<T>的约束)。看起来像这样:

static bool almostIncreasingSequence<T>(IEnumerable<T> sequence) where T : IComparable<T>
{
    bool foundOne = false;
    int i = 0;
    T previous = default(T), previousPrevious = default(T);

    foreach (T t in sequence)
    {
        bool deleteCurrent = false;

        if (i > 0)
        {
            if (previous.CompareTo(t) >= 0)
            {
                if (foundOne)
                {
                    return false;
                }

                // So, which one do we delete? If the element before the previous
                // one is in sequence with the current element, delete the previous
                // element. If it's out of sequence with the current element, delete
                // the current element. If we don't have a previous previous element,
                // delete the previous one.

                if (i > 1 && previousPrevious.CompareTo(t) >= 0)
                {
                    deleteCurrent = true;
                }

                foundOne = true;
            }
        }

        if (!foundOne)
        {
            previousPrevious = previous;
        }

        if (!deleteCurrent)
        {
            previous = t;
        }
        i++;
    }

    return true;
}

当然，如果您愿意将原始序列复制到一个临时数组中(如果尚未复制的话)，则可以轻松地使基于数组的版本通用，这将使代码简单得多，但仍然通用。这仅取决于您的优先级。

附录:

LINQ方法和线性方法(例如上面的我的方法)之间基本的性能差异是显而易见的，但是我很好奇，想对这种差异进行量化。因此，我使用随机生成的序列进行了一些测试，以大致了解两者之间的差异。

我执行了两个版本的测试:第一个，我运行了1000次试验的循环，其中序列的长度可以在10到100个元素之间。第二个是10,000个试验，序列长度在100到1000个元素之间。我执行第二个版本，是因为在我的笔记本电脑上完成了1000个较短序列的试验的全部测试，这些试验在不到1/2秒的时间内完成，对于我而言，时间太短，无法对结果的有效性充满信心。

在第一个版本中，代码花费约1毫秒调用检查的线性方法，并花费约30毫秒调用LINQ方法，以使速度相差30倍。将试验数量增加到10,000证实了结果；每种方法的时间几乎精确地定为10倍，而相差30倍。

在第二版中，差异接近400倍。线性版本花费了大约0.07秒，而LINQ版本花费了30秒。

不出所料，序列越长，差异越严重。对于非常短的序列，不仅代码不太可能在序列检查逻辑中花费大量时间，而且线性方法和LINQ方法之间的差异也将相对较小。但是随着序列变得更长，LINQ版本的差异将趋向于非常差的性能，而线性版本仍然是出色的表现。

LINQ版本非常易读和简洁。因此，在输入总是总是比较短的情况下(最多大约十二个或两个元素)，我会选择LINQ版本。但是，如果我希望使用更长的数据来例行执行此测试，则可以避免使用LINQ，而坚持使用效率更高的线性方法。

关于随机生成的序列的注释:我编写了代码，以生成具有所需长度的非负数的单调递增序列，然后将其插入0到2个(包括两个值)具有 int.MinValue或 int.MaxValue值的新元素(包括也为每次插入随机选择)。这样，三分之一的测试涉及的序列是微不足道的有效序列，三分之一的序列涉及需要找到正确的单个元素才能删除的序列，而三分之一的序列则无效(即不满足可以单调递增的要求最多删除一个元素)。