java - 由于我的黑客等级解决方案超时而终止

Question

大家好，请检查问题HackerRank 问题陈述

这是我对上述问题的解决方案（链接）

static int migratoryBirds(List<Integer> arr) {
    int ar[]=new int[arr.size()];
    for(int i=0;i<arr.size();i++){
        ar[i] = Collections.frequency(arr,arr.get(i));
        // ar[i] = obj.occuranceOfElement(arr,arr.get(i));
    }
    int maxAt = 0;
    for (int i = 0; i < ar.length; i++) {
        maxAt = ar[i] > ar[maxAt] ? i : maxAt;
    }
    return arr.get(maxAt);
}

当数组大小较大时，我的代码无法处理，例如数组中的 17623 个元素。

因超时而终止

问题出在第二个 for 循环中，它遍历数组并为我提供数组中最大数的索引。有没有其他方法可以提高性能。

标签： javaarraysperformancecollections

Answer 1

您的问题是对 Colletions.frequency 的调用，这是一个 O(N) 操作。当您从循环内部调用它时，它变为 O(N²) 并且会占用您所有的时间。

另外，你确定你收到了哪个 List 实现？如果实现是 LinkedList，您调用 list.get(i) 也可能是 O(N)。

本练习的目标是计算输入中每​​个值的频率。您需要一个地方来存储和增加每个值的出现次数，并且您需要存储输入的最大值。

您还跳过了规范的关键部分。输入有限制，这使得解决问题比你现在想象的更容易。