检查整数序列是否在增加

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/20秒的时间内完成,这对于我对结果的有效性有信心的时间太短.

对于第一个版本,代码花了大约1ms来调用检查的线性方法,大约30ms调用LINQ方法,速度差为30倍.将试验次数增加到10,000次证实了结果; 对于每种方法,时间几乎完全缩放10倍,保持相差30倍.

在第二个版本中,差异接近400 x.线性版本花了大约0.07秒,而LINQ版本需要30秒.

正如所料,序列越长,差异越大.对于非常短的序列,不仅代码不太可能在序列检查逻辑中花费太多时间,线性和LINQ方法之间的差异将相对较小.但随着序列变得越来越长,LINQ版本的差异将导致性能非常差,而线性版本仍然表现出色.

LINQ版本非常易读且简洁.因此,在输入总是相对较短的情况下(最多只有十几个元素),我会使用LINQ版本.但是如果我希望用比这更长的数据定期执行这个测试,我会避免使用LINQ并坚持使用更高效的线性方法.

关于随机生成的序列的注释:我编写了代码以生成单调递增的非负数序列,具有所需长度,然后插入0到2(包括)具有值int.MinValue或int.MaxValue(也随机)的新元素选中,每次插入).通过这种方式,三分之一的测试涉及非常有效的序列,第三部分涉及需要找到正确的单个元素去除的序列,第三部分无效(即不符合可以单调增加的要求)删除最多一个元素).

Answer 2

更新：修复了与我使用生成子序列的方式相关的错误Except。明显的问题是，当原始序列包含重复项时生成的子序列可能是错误的；重复项目的所有位置都可能被删除。

这个问题看似简单，但你很容易陷入 if 和 else 的循环中，永远无法完全正确。

解决这个问题的最佳方法是退后一步，了解您所要求的条件的真正含义。几乎严格递增的序列是这样一种序列：在通过删除一项而创建的所有可能的子序列中，至少有一个必须是严格递增的。

好吧，这似乎是合理的推理，而且很容易实现，所以让我们这样做：

首先，一个简单的方法告诉我们给定的序列是否严格递增：

private static bool IsStrictlyIncreasing<T>(this IEnumerable<T> sequence)
    where T : IComparable<T>
{
    using (var e = sequence.GetEnumerator())
    {
        if (!e.MoveNext())
            return true;

        var previous = e.Current;

        while (e.MoveNext())
        {
            if (e.Current.CompareTo(previous) <= 0)
                return false;

            previous = e.Current;
        }

        return true;
    }
}

现在我们需要一个辅助方法来生成删除一项的所有可能的子序列（如上所述，如果具有值相等语义，则简单地使用Except不会削减它）：T

private static IEnumerable<IEnumerable<T>> GenerateSubsequences<T>(
    this IEnumerable<T> sequence)
    => Enumerable.Range(0, sequence.Count())
                 .Select(i => sequence.Take(i)
                                      .Concat(sequence.Skip(i + 1)))

现在，我们只需检查所有子序列并找到至少一个严格递增的子序列：

public static bool IsAlmostStrictlyIncreasing<T>(this IEnumerable<T> sequence)
    where T : IComparable<T>
    => sequence.GenerateSubsequences()
               .Any(s => s.IsStrictlyIncreasing());

应该可以做到这一点。