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

大家好，请检查问题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个元素。


由于超时终止


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

最佳答案

您的问题在这部分中：

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;
}

关于java - 由于我的黑客等级解决方案超时而终止，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53700710/