有什么方法可以使下面的 Java 代码的执行速度更快？

Question

我的Java代码如下。boolean almostIncreasingSequence(int[] sequence) {        Integer[] arr = new Integer[sequence.length];        for(int ctr = 0; ctr < sequence.length; ctr++) {            arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value        }        System.out.println("Integer :: " + arr);        List<Integer> al = new ArrayList<Integer>();         // adding elements of array to arrayList.         Collections.addAll(al, arr);        System.out.println("list :: " + al);        int save, flag = 0;        for(int i=0; i<al.size(); i++) {            save = al.get(i);            al.remove(i);            if(al.size()==1) return true;            for(int j=0; j<al.size()-1; j++) {                if(al.get(j+1) > al.get(j)) {                    flag = 0;                    continue;                }                else {                    flag = 1;                    break;                }            }                if(flag == 0) {                    return true;                }                al.add(i,save);            }        if(flag == 1)            return false;        return true;    }该代码用于解决问题“给定整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列。”对于某些测试用例，它显示执行此操作需要 3 秒以上。但是，我不确定在哪里可以进行更改以更快地执行它。我无权访问测试用例。在这里，我创建了 2 个 for 循环，因为在第一个循环中，我正在生成将删除每个索引的列表，在第二个循环中，我正在迭代已删除元素的新列表。像示例数组是 {1,2,4,3} 然后在第一个循环中我创建一个数组，它将是 {2,4,3},{1,4,3},{1,2,3}和{1,2,4}。在第二个循环中，我遍历所有这 4 个数组以比较每个元素。

Answer 1

主要观察结果是列表可以分解为 3 个（可能为空）部分：

list = list[0..s) + list[s..e) + list[e..length)

Wherelist[0..s)和list[e..length)是严格增加的列表，并且list[s..e)是介于两者之间的东西。

因为您知道这些前缀和后缀列表是严格递增的，所以您不需要在这些列表中重复检查此属性。

您可以为约束选择任何值s，但假设您选择的值尽可能大，并且尽可能小。e0 <= s <= e < lengthse

如果列表具有所需的整体属性，则：

• s == length，因此列表已经严格增加而没有删除任何内容。

• list[s..e)长度最多为 1 ( e-s == 1)，并且list[0..s) + list[e..length)严格递增。您可以通过简单的比较来检查这一点list[s-1] < list[e]。

• list[s..e)为空 ( s == e)，因此您要求list[0..s-1) + list [e..length)（即删除前缀的最后一个元素）或list[0..s) + list[e+1..length)（即删除后缀的第一个元素）严格递增。检查(s == 0 || list[s-1] < list[e])和(e+1 == length || list[s] < list[e+1])分别。

• 如果list[s..e)有超过 1 个元素 ( e-s > 1)，则需要删除多个元素才能为列表提供所需的属性。

查找s和e：

s从零处的整数指针开始。递增它直到它到达末尾，或者它指向list[0..s)一个严格递增列表的元素，但list[0..s+1)不会。

e从列表长度的整数指针开始。减少它，而e>s不会list[e-1..length)是一个严格增加的列表。

Answer 2

更新 2：也尝试此代码（最多 2 个循环） 进一步优化是可能的，但仍会产生 O(n) 时间

public class TstList {

public static boolean compute(int a[]) {

    if (compute_1(a))

        return true;

    return compute_2(a);

}

public static boolean compute_1(int a[]) {

    if (a.length < 2)

        return true;

    int previous = a[0];

    int counter = 0;

    for (int i = 1; i < a.length; i++) {

        if (previous < a[i]) {

            previous = a[i];

            continue;

        } else {

            if (i == 1)

                previous = a[i];

            else

                previous = a[i - 1];

            counter++;

        }

        if (counter > 1)

            return false;

    }

    return true;

}

public static boolean compute_2(int a[]) {

    if (a.length < 2)

        return true;

    int previous = a[0];

    int counter = 0;

    for (int i = 1; i < a.length; i++) {

        if (previous < a[i]) {

            previous = a[i];

            continue;

        } else {

            previous = a[i];

            counter++;

        }

        if (counter > 1)

            return false;

    }

    return true;

}

public static void main(String arg[]) {

    System.out.println(compute(new int[] { 1, 2, 3, 4, 6 }));       \\1

    System.out.println(compute(new int[] { 1, 2, 3, 1, 4, 6 }));    \\2

    System.out.println(compute(new int[] { 1, 2, 1, 3, 1, 4, 6 })); \\3

    System.out.println(compute(new int[] { 1, 2, 3, 4, 6, 3 }));    \\4

    System.out.println(compute(new int[] { 3, 2, 1 }));             \\5

    System.out.println(compute(new int[] { 10, 1, 2, 3, 4, 5 }));   \\6

    System.out.println(compute(new int[] { 1, 2, 5, 3, 5 }));       \\7

}

}

输出

true  \\1

true  \\2

false \\3

true  \\4

false \\5 

true  \\6

true  \\7

Answer 3

我会选择这个。

编辑：提供更新的解决方案。它很快，但可读性不好。我还包含了一个 main() 类，其中包含我测试此代码的一些标准序列。（以测试人员很容易验证这一点的格式添加任何额外的案例）。

/**

 * Returns true if by removing maximum 1-entry the sequence can be strictly increasing.If not, it returns false. Doesn't check

 * if sequence is empty

 */

private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing(final int[] sequence)

{

    boolean isFirstNonDecreasingSequence = true;

    final int length = sequence.length;

    int maxValue = sequence[0];

    for (int i = 1; i < length; i++)

    {

        if (sequence[i] <= maxValue)

        {

            if (isFirstNonDecreasingSequence == true)

            {

                if ((i + 1) < length) // check this is not the last element

                {

                    if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit

                    {

                        // [i-1] is a local peak. Remove [i-1]

                        if (i > 1)

                        {

                            if (sequence[i] <= sequence[i - 2])

                            {

                                return false;

                            }

                        }

                        maxValue = sequence[i];

                    }

                    // else { // [i] is a local pit. Remove [i]. maxValue is not updated. }

                    isFirstNonDecreasingSequence = false;

                }

            }

            else

            {

                return false;

            }

        }

        else

        {

            maxValue = sequence[i];

        }

    }

    return true;

}

public static void main(final String[] args)

{

    final List<int[]> testInputs = new ArrayList<>();

    final List<Boolean> correctResults = new ArrayList<>();

    final List<Boolean> results = new ArrayList<>();

    testInputs.add(new int[] { 0 }); // single-element sequence

    correctResults.add(true);

    testInputs.add(new int[] { 0, 0 }); // two-element sequence

    correctResults.add(true);

    testInputs.add(new int[] { 0, 0, 0 }); // constant sequence

    correctResults.add(false);

    testInputs.add(new int[] { 1, 2, 3, 4, 6 }); // strictly increasing

    correctResults.add(true);

    testInputs.add(new int[] { 3, 2, 1 }); // strictly decreasing

    correctResults.add(false);

    testInputs.add(new int[] { 10, 1, 2, 3 }); // first value (10) should be removed

    correctResults.add(true);

    testInputs.add(new int[] { 1, 2, 3, 1 }); // last value (1) should be removed

    correctResults.add(true);

    testInputs.add(new int[] { 1, 2, 5, 3, 5 }); // peak (5) (inner value should be removed)

    correctResults.add(true);

    testInputs.add(new int[] { 1, 2, 3, 10, 4, 4, 5 }); // peak (10) followed by constant (4)

    correctResults.add(false);

    testInputs.add(new int[] { 1, 2, 3, 1, 4, 6 }); // pit (1) (inner value should be removed)

    correctResults.add(true);

    testInputs.add(new int[] { 5, 6, 2, 6, 7 }); // pit (2) that does not recover

    correctResults.add(false);

    testInputs.add(new int[] { 5, 0, 3 }); // first value should be removed

    correctResults.add(true);

    testInputs.add(new int[] { 5, 6, 1, 2 }); // sequence downward gap (pit)

    correctResults.add(false);

    for (int i = 0; i < testInputs.size(); i++)

    {

        results.add(checkIfRemovingMaxOneElementItIsStrictlyIncreasing_NoAssignment(testInputs.get(i)));

        if (correctResults.get(i) == results.get(i))

        {

            System.out.println("Test case: " + i + " successful.");

        }

        else

        {

            System.out.println("Test case: " + i + " should be: " + correctResults.get(i) + " but was: " + results.get(i));

            System.out.println("Test case: " + i + " input array: " + Arrays.toString(testInputs.get(i)));

        }

    }

}

此外，如果您不关心特定值是否被破坏，则可以避免使用额外的变量：

private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing_WithoutAssignment(final int[] sequence)

{

    boolean isFirstNonDecreasingSequence = true;

    final int length = sequence.length;

    for (int i = 1; i < length; i++)

    {

        if (sequence[i] <= sequence[i - 1])

        {

            if (isFirstNonDecreasingSequence == true)

            {

                if ((i + 1) < length) // check this is not the last element

                {

                    if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit

                    {

                        // [i-1] is a local peak. Remove [i-1]

                        if (i > 1)

                        {

                            // Check if by removing [i-1] the sequence is actually increasing

                            if (sequence[i] <= sequence[i - 2])

                            {

                                return false;

                            }

                        }

                    }

                    else

                    {

                        // [i] is a local pit. Remove [i]

                        sequence[i] = sequence[i - 1];

                    }

                    isFirstNonDecreasingSequence = false;

                }

            }

            else

            {

                return false;

            }

        }

    }

    return true;

}

在这两个版本中，代码中都有很多 if。这是真的，但它们只会在序列第一次检测到两个连续值的非递增序列时执行。所以在性能方面这应该没问题。

至于逻辑：

当它在索引[i]处检测到：A[i-1]>=A[i]时，它确定它是否在一个峰值之后（因此A[i-1]是“异常”高并且应该从序列中删除）或者它在一个坑内（A[i] 太低，应该从序列中删除）。