时间戳

首页 > 解决方案 > 使用Java检查序列是否几乎严格按升序排列

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

问题描述

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

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

例如，

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

almostIncreasingSequence(sequence) = false

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

对于序列=[1, 3, 2]输出应该是

almostIncreasingSequence(sequence) = true

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

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

面试官想要的概念算法如下与Java：

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);
}

但我没有得到sequence[i]与sequence[i+1]和进行比较的部分sequence[i+2]来增加计数器seq1和seq2。这如何涵盖所有情况？

标签： java

解决方案

这如何涵盖所有情况？

它不是。

这个算法是错误的。

考虑输入数组

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

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

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

一个可能的解决方案：

  1. 遍历数组，比较每对相邻元素。
  2. 第一次找到不严格递增的对时（a[i] >= a[i+1]），您必须检查删除 a[i] 或 a[i+1] 是否会使数组严格递增.
    • 如果删除 a[i]，则必须确保 a[i-1] < a[i+1]。
    • 如果删除 a[i+1]，则必须确保 a[i] < a[i+2]。
    • 如果此验证失败，则返回false.
  3. 否则，您将继续测试阵列的其余部分。
    • 如果您发现另一对不严格增加，则返回 false。
    • 否则你返回真。

推荐阅读