Как найти наиболее распространенное число во входе?

Question

Это очень абстрактное объяснение того, что я делаю:

Скажем, у меня есть текстовый файл, полный номеров, разделенных символами новой строки. Прямо сейчас, я беру эти цифры и помещаю их в map<int, int>, где ключ - это число, а значение - это частота.

Моя конечная цель - это список номеров, отсортированных по частоте. Как я могу это сделать? Обратите внимание, что частота, очевидно, может появляться более одного раза. То, как я думал, это сделать struct, содержащий как число, так и его частоту, и определить <, чтобы он никогда не возвращал равенства. Затем я перебирал через карту, помещая все элементы в эту структуру, а затем в набор.

Answer 1

После того, как вы построили частотную карту, скопировать ее пары в std::vector<std::pair<int, int> > затем std::sort последних с версией 3-арга из std::sort, который принимает компаратор в качестве третьего арг; в качестве компаратора вы можете использовать тот, который сравнивает поля .second первых пар, и .first (если вы хотите) только для устранения неоднозначности упорядочения пар, поля которых равны .second (но я не думаю, что вам действительно нужно последний бит, так как вы не заботитесь о заказе для случаев с одинаковой частотой, не так ли?).

Answer 2

Если это просто операция вы хотите сделать на своем собственном (а не компонента вы хотите использовать), наиболее практичным способом для меня было бы сделать что-то вроде этого:

sort <filename> | uniq -c | sed 's/^[ \t]*//' | sort -rn 

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

---

EDIT: вроде»сортирует файл,„Уник“группы всех последовательных линий, которые одинаковы в пару [частота] [пункт] пары, например

12 
12 
24 
25 
25 
25 

становится

2 12 
    1 24 
    3 25 

Затем я удаляю конечное пространство с помощью «sed» (если это не работает, это потому, что иногда возникает проблема с тем, как символ табуляции находится в putted), то я сортирую вывод по частоте (опция «n» запрашивает числовую сортировку вместо лексикографической; опция «r» запрашивает обратную сортировку).

Если вы хотите выбрать другое поле для сортировки (скажем, потому что число, на которое вы действительно заинтересованы в подсчете частоты, является полем THIRD строки с разделителями табуляции), вы можете использовать функцию выбора «сортировка» :

sort -t'\t' -k3 <filename> | ... 

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

---

EDIT 2: здесь есть линия, чтобы сделать это в соответствии с четвертым полем (и удалить все другие поля)

cut -d'\t' -f4 <filename> | sort | uniq -c | sed 's/^[ \t]*//' | sort -rn 

Answer 3

итерацию по std:pair из std::map и вставить их в a std::priority_queue. Используйте функцию сравнения из значения.

Как только у вас есть очередь приоритетов, вы можете перебирать ее.