каковы быстрые алгоритмы поиска дубликатов элементов в коллекции и их группировки?

Предположим, что у нас есть набор элементов, и эти элементы имеют только равный оператор. Таким образом, их невозможно сортировать.

как вы можете выбрать тех, у кого есть дубликаты, и поместить их в каждую группу с минимальным количеством сравнения? желательно на C ++, но алгоритм более важен, чем язык. Для примера, приведенного {E1, E2, E3, E4, E4, E2, E6, E4, E3}, я хочу извлечь {E2, E2}, {E3, E3}, {E4, E4, E4}. какую структуру данных и алгоритм вы выберете?

РЕДАКТИРОВАТЬ

Мой сценарий, если двоичные данные 1 равны двоичным данным 2, мы можем сказать, что эти два элемента идентичны. Но, только = и ! = Логично

element 1: 4 0 obj <> stream .....binary data 1.... endstream endobj element 2: 5 0 obj <> stream .....binary data 2.... endstream endobj 

Достаточно найти любой произвольный предикат P такой, что P(a,a)==false , P(a,b) && P(b,a)==false , P(a,b) && P(b,c) означает, что P(a,c) и !P(a,b) && !P(b,a) влечет a == b . Меньше-то удовлетворяет этому свойству, как, следовательно, больше. Но они далеки от единственных возможностей.

Теперь вы можете сортировать свою коллекцию по предикату P , и все равные элементы будут смежными. В вашем случае определите P(E1,E2)=true, P(E2,E3)=true и т. Д.

Для вашего ответа, хотя я не уверен на 100%, что вы хотите, чтобы это было только.

Если вы хотите, чтобы хороший алгоритм попытался создать двоичное Binary search tree . так как это группа, и в соответствии с BST properties вы можете легко группировать элементы.

Например

 BST() { count = 0; if(elementinserted) count = 1; if(newelement == already inserted element) { count++; put element in array upto count value; } } 

Надеюсь, это объяснение поможет вам.

Если у вас есть тест равенства, у вас нет надежды.

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

Существует n(n+1)/2 второго типа. Каждый может отличаться только от первого путем конкретного сравнения. Это означает, что в худшем случае вы должны выполнить все n(n+1)/2 сравнения: exhastive search по всем парам.

Что вам нужно сделать, так это выяснить, что еще вы действительно можете сделать, поскольку равенство является исключительно редким.