Алгоритм для карты & lt; int, vector & lt; int & gt; & GT;

Question

Алгоритм для карты & lt; int, vector & lt; int & gt; & GT;

Мне трудно придумать эффективный алгоритм для решения проблемы с вектором карты.

Скажи у меня есть карта > и я хотел бы узнать, сколько раз встречается целое число во всех векторах карты, и, если оно встречается в заранее заданном количестве, удалите его значение из остальных векторов (надеюсь, это имеет смысл), вот быстрый пример :

ключевые значения

1 — <2,3,4,4,5>

2 — <2,3,3,4,5>

3- <2,3,3,4,6>

В этом случае, скажем, я хотел удалить 4 из всех векторов, если это произошло более трех раз. Полученная карта будет выглядеть так:

1 — <2,3,4,4,5>

2 — <2,3,3,4,5>

3- <2,3,3,DEL,6>

Я ищу эффективный алгоритм для этой проблемы, и мне просто интересно, есть ли у кого-нибудь идеи. (Я работаю в C ++, но я знаю, что Java или псевдокод это круто).

Спасибо за любую помощь

Примечание: векторы не сортируются в реальной жизни только в этом примере.

1

algorithm big-o c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Однако, учитывая ваши точные потребности и использование контейнеров, могут быть доступны альтернативные подходы. Например, если vector на самом деле не нужно быть индексируемым, вы могли бы использовать multiset вместо этого, чтобы сохранить элементы отсортированы и обеспечить легкий подсчет и удаление.

2