超出时间异常java时间限制的问题

我要解决一个问题，函数“thor”接收3个数组列表和一个int，算法必须上传到一个页面，如果函数是正确的，在第一次测试页面返回预期的结果，但是继续测试时，返回“超过时间限制，代码用了太多cpu”。我需要帮助解决这个问题，谢谢！

import java.util.*;

public class microondas {
    public static long thor(ArrayList<Integer> a, ArrayList<Integer> f, ArrayList<Integer> p, int D) {
        long acumu,peso,altura,fuerza,distancia;
        acumu=0;
        for(int i=0;i<a.size();i++) {
                for(int s=0;s<p.size();s++) {
                    peso=p.get(s);
                    altura=a.get(i);
                    fuerza=f.get(i);
                    distancia=(altura*fuerza)/peso;
                    if(distancia>=D) {
                    acumu+=1;   
                }
            }
        }
        return acumu;
    }
}

如何节省内存？我认为二维颊部是问题所在。

在这段代码和可用的信息只有基本的微观优化是可能的：没有必要计算 altura / fuerza 因为这些变量依赖于第一个循环。此外，除以常量值可能会移到嵌套循环之外：

a.get(i) * f.get(i) / f.get(s) >= D is the same as a.get(i) * f.get(i) / D >= f.get(s)

public static long thor(ArrayList<Integer> a, ArrayList<Integer> f, ArrayList<Integer> p, int D) {
    long acumu = 0;
    int iters = 0;
    for (int i = 0, n = a.size(); i < n; i++) {
        long product = a.get(i) * f.get(i) / D;

        for (int peso : p) {
            if (product >= peso) {
                acumu++;
            }
            iters++;
        }
    }
    System.out.println("thor iterations: " + iters);

    return acumu;
}

但是，它不太可能帮助解决tle，因为此代码无论如何都有复杂性 O(N * M) 哪里 N 大小是 a / f 以及 M 大小是 p .
进一步优化可以是：
对产品清单进行预计算和排序，
排序列表 p 迭代列表时 p 记住最后一个有效的 peso 丢弃包含小值的尾部。
一些快捷方式是可能的：
如果最大产品小于最小产品 peso ，所有产品可报废，0退回；
如果最大的 peso 小于或等于最小积，结果为 product.size() * p.size() ```
public static long thorFaster(List a, List f, List p, int D) {
Collections.sort(p);
List products = new ArrayList<>();

for (int i = 0, n = a.size(); i < n; i++) {
    products.add(a.get(i) * f.get(i) / D);
}
Collections.sort(products, Collections.reverseOrder());
if (products.get(0) < p.get(0)) {
    return 0;
} else if (p.get(p.size() - 1) <= products.get(products.size() - 1)) {
    return p.size() * products.size();
}

long acumu = 0;
int iters = 0;

int lastP = p.size();
for (int i = 0, n = products.size(); i < n; i++) {
    for (int s = 0; s < lastP; s++) {
        iters++;

        int peso = p.get(s);
        if (peso <= products.get(i)) {
            acumu++;
        } else {
            lastP = s; // found limit
            break;
        }
    }
}
System.out.println("thorFaster iterations: " + iters);

return acumu;

}

测验：

List a = Arrays.asList(1, 0, 2, 3, 4, 5, 8);
List f = Arrays.asList(2, 3, 4, 4, 6, 1, 0);
List p = Arrays.asList(3, 4, 5, 8, 10);

System.out.println("thor: " + thor(a, f, p, 2));
System.out.println("thorFaster: " + thorFaster(a, f, p, 2));

输出：

thor iterations: 35
thor: 10
thorFaster iterations: 13
thorFaster: 10

超出时间异常java时间限制的问题

1条答案

相关问题

热门标签

最新问答