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

Question

大家好请检查问题HackerRank Problem Statement

这是我对上述问题的解决方案(链接)

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 个元素。

Terminated due to timeout

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

Answer 1

您的问题出在这部分:

for(int i = 0; i < arr.size(); i++)
    ar[i] = Collections.frequency(arr, arr.get(i));

这是 O(N²):Collections.frequency() 遍历整个列表以仅计算一个元素的频率。您可以手动遍历列表以计算所有元素的频率。

此外，只有 5 只鸟，所以你只需要 5 个长度的数组。

static int migratoryBirds(int[] arr) {
    int max = 1;
    int[] freq = new int[6];

    for (int val : arr)
        freq[val]++;

    for (int i = 2; i < freq.length; i++)
        max = freq[i] > freq[max] ? i : max;

    return max;
}