时间戳

首页 > 解决方案 > 提高竞争性编程问题的性能

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

问题描述

串联电路中有从 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;
}

有人可以指出可以做些什么来提高我的代码的性能吗？任何指针都会非常有帮助！！！

标签： javaarraysalgorithm

解决方案

有了这些问题，您有时可以通过以不同方式计算答案来消除一些所需的循环。

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

例如：

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

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

推荐阅读