提高竞争性编程问题的性能

Question

串联电路中有从1到N的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 是最大的数字。

答案是最大数字等于灯泡打开的次数。

Answer 2

@fgb指出了一个简单的标准：当max == count时将true。

然后，您只需要计算最大值和计数值。

public static int solution(int [] xs) {
int max = xs[0];
int count = 0;
int trues = 0;
for(int x: xs) {
max = Math.max(max, x);
count = count + 1;
if(max == count)
trues = trues + 1;
}
return trues;
}