Самый быстрый алгоритм для поиска частот каждого элемента массива реалов?

Question

Проблема состоит в том, чтобы найти частоты каждого элемента массива реалов.

double[] a = new double[n] 
int[] freq = new int[n] 

Я придумал два решения:

Первое решение O (N^2):

for (int i = 0; i < a.length; i++) { 
    if (freq[i] != -1) { 
    for (int j = i + 1; j < a.length; j++) { 
     if (a[i] == a[j]) { 
     freq[i]++; 
     freq[j] = -1; 
     } 
    } 
    } 
} 

Второе решение O (NlogN):

quickSort(a, 0, a.length - 1); 

freq[j] = 1; 
for (int i = 0; i < a.length - 1; i++) { 
    if (a[i] == a[i + 1]) { 
    freq[j]++; 
    } 
    else { 
    j = i + 1; 
    freq[j] = 1; 
    } 
} 

ли существует ли более быстрый алгоритм для этой задачи (O (n))? Благодарим вас за любую помощь, которую вы можете предоставить.

Answer 1

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

Map<Double, Long> freqCount = DoubleStream.of(reals).boxed() 
     .collect(Collectors.groupingBy(d -> d, Collectors.counting())); 

Это использует совсем немного памяти, но это O (п).

В качестве альтернативы можно использовать следующие в качестве первого прохода

NavigableMap<Double, Long> freqCount = DoubleStream.of(reals).boxed() 
     .collect(Collectors.groupingBy(d -> d, TreeMap::new, Collectors.counting())); 

Это будет рассчитывать все значения, которые точно так же, и вы можете использовать стратегию группировки объединить двойные значения, которые почти то же самое , но следует считать равными для ваших целей. Это O (N log N)

Answer 2

Позвольте мне начать с того, что проверка подлинности double s не является хорошей практикой. Подробнее см .: What every programmer should know about floating points.
Вы должны использовать более надежные сравнения double.

Теперь, когда мы закончим с этим, давайте обратимся к вашей проблеме.
Вы имеете дело с изменением Element Distinctness Problem с числами с плавающей запятой.

Вообще говоря, в рамках модели вычисления алгебраического дерева нельзя сделать это лучше, чем Omega(nlogn) (ссылки в этой теме: https://stackoverflow.com/a/7055544/572670).

Однако, если вы собираетесь придерживаться double чеки идентичности (пожалуйста, нет), вы можете использовать более сильную модель и хэш-таблицу для достижения O(n) решения, сохраняя хэш-таблицу на основе histogram (реализовано в виде HashMap<Double,Integer>), и когда вы закончите, просмотрите гистограмму и введите ключ самого высокого значения.
(Пожалуйста, не делайте этого)

---

Существует сложный способ сделать достичь O(n) времени основанного на хеширования, даже при работе с плавающей точкой. Это основано на добавлении элементов к нескольким записям хеш-таблицы и при условии, что хеш-функция принимает диапазон элементов [x-delta/2,x+delta/2) к тому же значению хэша (поэтому он хеширует куски [x1,x2)->h1, [x2,x3)->h2, [x3,x4)->h3, ....). Затем вы можете создать хеш-таблицу, где элемент x будет хэширован до трех значений: x-3/4delta, x, x + 3/4delta.
Это гарантирует при проверке равного значения позже, он будет иметь совпадение, по крайней мере, в одном из трех мест, в которые вы помещаете элемент.

Это значительно сложнее реализовать, но оно должно работать. Вариант этого можно найти в cracking the code interview, математический, вопрос 6. (Просто убедитесь, что вы смотрите на выпуске 5, ответ в редакции-неверно и был зафиксирован в новой редакции)

---

В другой стороне обратите внимание: вам не нужно реализовывать свой собственный вид. Использовать Arrays.sort()

Answer 3

Использование Trie будет выполняться в почти линейном времени, потому что вставки будут очень быстрыми (или такими же быстрыми, как и порядок вашего реального номера).

Сортировка и подсчет определенно слишком медленны, если все, что вам нужно, это частоты. Ваш друг - trie: https://en.wikipedia.org/wiki/Trie

Если вы использовали Trie, то вы преобразовали бы каждое целое число в String (достаточно простое на Java). Сложность вставки в Trie немного зависит от реализации, но в целом она будет пропорциональна длине строки.

Если вам нужна реализация TRIE, я предлагаю смотреть в реализацию Роберта Седжвика в ходе его алгоритма здесь:

http://algs4.cs.princeton.edu/52trie/TrieST.java.html