Завершено из-за тайм-аута для моего решения хакерского ранга

Question

Привет всем, пожалуйста, проверьте проблему Постановка проблемы HackerRank

Это мое решение для вышеуказанной проблемы (ссылка)

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

Мы можем определить номер типа наиболее распространенной птицы в одном цикле.Это имеет временную сложность 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.Если два разных типа птиц имеют максимальную частоту , то устанавливается нижний тип ( с наименьшим идентификационным номером ).

Answer 2

Ваша проблема в этой части:

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

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

Answer 4

Ваша проблема - вызов Collections.frequency, который является операцией O (N).Когда вы вызываете его из цикла, он становится O (N²), и это занимает все ваше время.

Кроме того, вы уверены, какое значение List вы получите?Вы вызываете list.get (i), который также может быть O (N), если реализация представляет собой LinkedList.

Цель этого упражнения - вычислить частоту каждого значения за один проход для ввода.Вам нужно место, где вы храните и увеличиваете число вхождений для каждого значения, и вам нужно хранить наибольшее значение ввода.

Вы также пропустили важную часть спецификации.Входные данные имеют пределы, которые облегчают решение проблемы, чем вы думаете сейчас.