Режим нахождения массива в O (n)

Question

Я думал, что понял это правильно, чтобы найти режим в 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;
}

Куда я иду не так?Спасибо

Answer 1

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

Answer 2

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