java 降低游戏程序的时间复杂度

vc9ivgsu 于 2022-12-28 发布在 Java

关注(0)|答案(2)|浏览(150)

亚当想从呈直线排列的建筑物的顶部观看足球比赛。
1.如果在Adam的前面存在最多K[i]个建筑物，且高度小于或等于ith个建筑物的高度，则Adam可以从ith个建筑物的顶部观看足球比赛。
1.如果亚当前面有任何建筑物的高度超过ith位置建筑物的高度，那么他不能从这个ith建筑物看到比赛。
数一数亚当能从楼顶看到比赛的建筑物的位置。

- 示例：**两个数组长度相同。

B (Buildings) = [2,1,3] represents the height of buildings
K = [1,2,1]

- 答案：**1
- 说明：**

For B[0] = 2 we have K[0] = 1. The number of buildings in front of it that have a height smaller than or equal to 2 is 0. This is <= K[0] So Adam can see the match.

For B[1] = 1, we have K[1] = 2. The number of buildings in front of it that have a height smaller than or equal to 1 is 0. But B[0] = 2 so Adam cannot see the match.

For B[2] = 3, we have K[2] = 1. The number of buildings in front of it that have a height smaller than or equal to 3 is 2. But this value is >= K[2] i.e 1 so Adam cannot see the match

The total positions where Adam can see the match is 1.

- 制约因素：**

Array size is 1 to 10^5
Each element in Arrays is 1 to 10^5

时间复杂度为O（n^2）。

public static int process(int[] buildings, int[] K) {
    int n = buildings.length;
    int answer = 0;
    for(int i=0; i<n; i++) {
        int count = 0;
        boolean valid = true;
        for(int j=i-1; j>=0; j--) {
            if(buildings[j] <= buildings[i]) count++;
            if (buildings[j] > buildings[i]) {
                valid = false;
                break;
            }
        }
        if(valid && count <= K[i]) answer++;
    }
    return answer;
}

这个程序对于小数组有效，但是对于大数组无效，因为我的程序的时间复杂度是O（n^2）。
解决这个问题的更好方法是什么？如何降低时间复杂度？

Java

来源：https://stackoverflow.com/questions/74880749/reduce-time-complexity-of-game-program

2条答案

按热度按时间

jogvjijk1#

你有两个条件，我们一个一个看，但我们将从第二个开始：
第二个条件可以解释为第i栋建筑物是前面任何其他建筑物中最高的建筑物。这可以通过检查第i个位置的最大高度并在进行时更新它来实现。
如果第二个条件为真，则意味着在第i栋建筑物前面有i-1栋建筑物等于或小于它（如果像array中那样从0开始计数，则为i而不是i-1）。因此，只有当k[i]大于（i-1）时，第一个条件才为真，您只需在它们之间进行比较。
下面是java中的代码：

import java.util.*;
class HelloWorld {
    public static void main(String[] args) {
        List<Integer> buildings = Arrays.asList(2, 1, 3);
        List<Integer> K = Arrays.asList(1, 2, 1);
        System.out.println(process(K, buildings));
    }

    
    public static Integer process(List<Integer> K, List<Integer> buildings){
        Integer maxHightBuilding = buildings.get(0);
        Integer sum = 0;
        for(Integer i = 0; i < buildings.size(); i++){
            if(buildings.get(i) >= maxHightBuilding ){
                maxHightBuilding = buildings.get(i);
                if(i <= K.get(i)){
                    sum++;
                }
            }
        }
        return sum;
    }
}

赞(0）回复(0）举报 2022-12-28

9jyewag02#

我认为如果你把最大值保留在实际指数之前，你可以检查这个值，当你的指数超过最大值时，你可以更新它。
所以从数组末尾开始找最大的值。
HF！

赞(0）回复(0）举报 2022-12-28