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

Question

大家好，请检查问题黑客排名问题陈述

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

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循环中，该循环遍历数组并给出数组中最大数字的索引。还有其他方法可以提高性能吗。

Answer 1

这里还有一个：

static int migratoryBirds(List<Integer> arr) {
    int freq[]=new int[6];
    for(int i=0;i<arr.size();i++){
        ++freq[arr.get(i)];
    }
    int maxAt = 1;
    for (int i = 2; i < freq.length; i++) {
        if (freq[i] > freq[maxAt]) {
            maxAt = i;
        }
    }
    return maxAt;
}

Answer 2

你的问题是调用Colletions.frequency，这是一个O（N）操作。当你从循环内部调用它时，它变成了O（N²），这消耗了你所有的时间。

还有，你确定你收到的是哪一份清单？您调用list.get(i ),如果实现是LinkedList，它也可能是O(N)。

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

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

Answer 3

你的问题在这一部分：

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

这是O(N):< code > 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;
}