Лучший способ найти повторяющиеся значения в наборе

Question

Каков наилучший способ найти наиболее повторяющиеся значения в наборе? Я хотел бы использовать однопроходный алгоритм, предполагая, что значения из области 1,2,3,4, .., m?

Если бы мне пришлось написать алгоритм для этого, как бы я это сделал?

Answer 1

SELECT value, COUNT(*) frequency
FROM table
GROUP BY value
ORDER BY COUNT(*) DESC

Answer 2

Сохраните их в хэш-таблице со счетчиком того, сколько раз каждый из них был сохранен (O (n)).
Затем выполните цикл по сегментам (O (n)).

Answer 3

По определению, набор содержит только уникальные значения. Таким образом, ответом должен быть сам набор, который можно «вычислить» за постоянное время. : -)

Серьезно, если предположить, что вы на самом деле работаете с кучей, списком, вектором или какой-то другой структурой данных, которая допускает дублирование, вероятно, самый быстрый способ решения проблемы - это ответ Майка Данлави, который заключается в использовании хеш-таблицы , Есть также некоторые методы, использующие деревья, которые вы можете использовать, которые используют последовательно более точные оценки. Я думаю, что такой подход будет O (n log n) (не так хорошо, как решение с хэш-таблицей), хотя, возможно, он может быть ниже, чем O (log n), если вы допустите некоторую статистическую ошибку.

Answer 4

SELECT  value
FROM    table
GROUP BY
        value
ORDER BY
        COUNT(*) desc
LIMIT 1