首页 文章

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

提问于
浏览
2

大家好,请检查问题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 回答

  • 3

    这是另一个:

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

    您的问题是调用Colletions.frequency,这是一个O(N)操作 . 当你从一个循环内部调用它时它变成O(N²)并消耗你所有的时间 .

    另外,您确定收到List的哪个列表?如果实现是LinkedList,则调用list.get(i),它也可能是O(N) .

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

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

  • 4

    你的问题在这部分:

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

    我们可以在一个循环中确定最常见鸟类的类型编号 . 这具有时间复杂度O(n) .

    static int migratoryBirds(int[] arr) {
        int highestFrequency = 0;
        int highestFrequencyBirdType = 0;
        int[] frequencies = new int[5]; // there are 5 bird types
    
        for (int birdType : arr) {
            int frequency = ++frequencies[birdType - 1];
            if (frequency > highestFrequency) {
                highestFrequency = frequency;
                highestFrequencyBirdType = birdType;
            } else if (frequency == highestFrequency && birdType < highestFrequencyBirdType) {
                highestFrequencyBirdType = birdType;
            }
        }
    
        return highestFrequencyBirdType;
    }
    

    对于数组 arr 中的每个元素,我们更新整个 highestFrequency 并存储表示 highestFrequencyBirdType 的相应值 . 如果两种不同的鸟类型具有最高频率,则设置较低类型(具有最小ID号) .

相关问题