使用Java检查序列是否几乎严格地按升序排列

Question

这是我面试问题的一部分。

给定一个整数序列作为一个数组，我必须确定是否可以通过从数组中移除不超过一个元素来获得一个严格递增的序列。

例如，

对于sequence=[1,3,2,1]，输出应该是

almostincreasingsequence(sequence)=false

在这个数组中没有一个元素可以被移除以得到一个>严格递增的序列。

对于sequence=[1,3,2]，输出应该是

almostincreasingsequence(sequence)=true

我们可以从数组中删除3，以得到严格递增序列[1,2]。或者，我们可以移除2以得到严格递增序列[1,3]。

如果可以从数组中移除一个元素以获得严格递增的序列，则函数必须返回true，否则返回false。

面试官想要的概念算法如下所示：

boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

但是我没有得到将序列[I]与序列[I+1]和序列[I+2]进行比较以增加计数器的部分，即seq1和seq2。这是如何涵盖所有案件的？




Answer 1

这是如何涵盖所有案件的？

它没有。

这个算法是错误的。

{1,2,3,5,4,6,7,9,8}

它不是一个几乎严格递增的序列，因为您必须删除至少两个元素（例如，4和9)，才能使它严格递增。

但是，您发布的代码将返回true，因为seq1+seq2==2(seq1是2，seq2是0)。

一个可能的解决方案：

• 遍历数组，比较每对相邻元素。
• 当您第一次发现一个不是严格递增的对(a[i]>=a[i+1])，您必须检查删除a[i]或[i+1]是否会使数组严格递增。
  • 如果删除[i]，则必须确保[i-1]
  • 如果删除一个[i+1]，则必须确保一个[i]
  • 如果验证失败，则返回false.
  • 如果发现另一对不是严格递增的，则返回false。
  • 否则返回true。