Блог

Главная - Вопросы по программированию - Режим поиска массива в O (n)

Режим поиска массива в O (n)

#java #algorithm #list #collections #time-complexity

#java #алгоритм #Список #Коллекции #временная сложность

Вопрос:

Я думал, что я правильно понял, чтобы найти режим в O (n). Но при синхронизации, похоже, он намного ближе к O (n * log (n)):

 public int mode(List<Integer> numList) {
    //Holds frequencies
    int[] frequencies = new int[Collections.max(numList) 1];

    for(int i=0; i<numList.size(); i  ) {
        frequencies[numList.get(i)] =1;
    }

    //Convert to List
    List<Integer> freqArray = IntStream.of(frequencies).boxed().collect(Collectors.toCollection(ArrayList::new));

    int maxFreq = Collections.max(freqArray);
    int mode = freqArray.indexOf(maxFreq);

    return mode;
}

Где я ошибаюсь? Спасибо

Комментарии:

1. То, что вы делаете, похоже на подсчет сортировки. Это не дало бы выходных данных для каждого ввода. [1,2147483647] или [-4,-5,-6]

2. Вы выделяете слишком много памяти для списков, которые распределены неравномерно. Лучше использовать HashMap для вычисления за O (n) время.

3. @vivek_23 Он просит помощи с домашним заданием. Он опубликовал этот вопрос ранее, и он был отклонен в небытие. Затем он удалил его. Его профессор специально попросил O(n * log(n)). Я рассказал ему, как сделать O (n) ранее.

Ответ №1:

Вы почти правы, поскольку большинство операций занимают до O (n) времени, за исключением, возможно, потоков. Они могут занимать больше времени, чем O (n), даже при прохождении через Iterable длины n. Подробнее здесь.

Ответ №2:

Как указано @Andronicus, вы можете избавиться от потоков и использовать чистые массивы, даже не списки. Но опять же, при вашем подходе ваша временная сложность не O(n) , а O(m) где m — максимальный элемент в вашем массиве. Также, как упоминалось в комментариях, ваш подход не будет работать для отрицательных значений. В таких случаях HashMap это ваш лучший выбор и в большинстве случаев гарантирует O(1) вставки / выборки для вычисления хэшей для простых типов, таких как целые числа.