提高竞争性编程问题的表现

Question

串联电路中有N个从1到N的灯泡。数组表示从0到（N-1）的灯泡编号。最初，所有灯泡均已关闭，并从阵列的索引0打开。我们需要计算在串联电路中打开灯泡的实例数量。

例如 ：

A = [2,1,3,5,4]应返回3

Explanation :-
Instant     Bulb number on      All bulbs in series switched on
0               2                   false
1               1,2                 true
2               1,2,3               true
3               1,2,3,5             false
4               1,2,3,4,5           true

因此，在3种情况下，灯泡已打开。数是3。

我的方法

1. 遍历数组的索引
2. 取数组的切片从0到索引
3. 对数组排序
4. 检查阵列是否已打开从0到index-1的所有灯泡
5. 计算实例数。

我的解决方案运行得很好，但是时间复杂度为O（n2）。我的解决方法如下

public int solution(int[] A) {
    // write your code in Java SE 8
    int counter = 0;

    for (int i = 0; i < A.length; i++) {
        int[] intermediate = Arrays.copyOfRange(A, 0, i);
        Arrays.sort(intermediate);

        if(checkIfOrdered(intermediate))
            counter++;
    }
    return counter;
}

private static boolean checkIfOrdered(int[] intermediate) {
    boolean flag = true;
    for (int i = 0; i < intermediate.length; i++) {
        if(intermediate[i] != (i +1) ){
            flag = false;
            break;
        }
    }
    return flag;
}

有人可以指出如何改善我的代码的性能吗？任何指针将非常有帮助！

Answer 1

遇到这些问题，有时可以通过不同地计算答案来消除一些所需的循环。

在您的示例中，似乎在每个瞬间都需要的唯一信息是灯泡的数量以及迄今为止找到的最大灯泡数量。

例如：

• 在瞬间1，有2个灯泡亮着，其中2个是最大的。
• 在瞬间3，有3个灯泡亮着，而3个是最大的。
• 在瞬间4，有5个灯泡亮着，其中5个是最大数量。

答案是最大次数等于灯泡上的次数。