大家好,请检查问题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);
}
my code is unable to handle when the array size is bigger,example 17623 elements in array .
由于超时而终止
问题出现在第二个for循环中,它迭代数组并给出数组中最大数字的索引 . Is there any other way that I could increase the performance.
4 回答
这是另一个:
您的问题是调用Colletions.frequency,这是一个O(N)操作 . 当你从一个循环内部调用它时它变成O(N²)并消耗你所有的时间 .
另外,您确定收到List的哪个列表?如果实现是LinkedList,则调用list.get(i),它也可能是O(N) .
本练习的目标是计算输入中一次传递中每个值的频率 . 您需要一个存储位置并增加每个值的出现次数,并且需要存储输入的最大值 .
您还跳过了规范的关键部分 . 输入有限制,这使得解决问题比您现在想象的更容易 .
你的问题在这部分:
这是 O(N²) :
Collections.frequency()
遍历整个列表以仅计算一个元素的频率 . 手动,您可以遍历列表来计算所有元素的频率 .此外,它只有5只鸟,所以你只需要5个长度阵列 .
我们可以在一个循环中确定最常见鸟类的类型编号 . 这具有时间复杂度O(n) .
对于数组
arr
中的每个元素,我们更新整个highestFrequency
并存储表示highestFrequencyBirdType
的相应值 . 如果两种不同的鸟类型具有最高频率,则设置较低类型(具有最小ID号) .