Какой самый быстрый способ поиска дубликатов в массиве без его сортировки?

Поместите элементы, которые вы видите в карту на основе хэша.

Начиная с задней части вашей коллекции, откройте назад и добавьте элементы в хэш-карту. Если элемент, который вы собираетесь добавить, не существует, установите его дублирующее значение в ноль и поместите 1 в карту для этого элемента. Если счет уже существует, то его дублирующее количество - это все, что есть на карте. Сохраните это число как количество дубликатов и увеличьте значение на карте.

vector<int> data({1, 2, 2, 3, 4});
unordered_map<int,int> count;
vector<int> res(data.size(), 0);
for (int i = data.size()-1 ; i >= 0 ; i--) {
    res[i] = count[data[i]]++;
}
for (int i = 0 ; i != res.size() ; i++) {
    cout << data[i] << " - " << res[i] << endl;
}

Демо на идеон.

Наиболее эффективный подход с точки зрения скорости, как правило, заключается в использовании частотной таблицы. Обычно это структура, которая отображает значение в число раз, когда оно происходит. В этом случае вы можете вместо этого сопоставить список/массив индексов (т.е. Индекс каждого места, где произошло значение).

Алгоритм будет проходить через каждый элемент и добавлять его в таблицу. Если найден дубликат, он добавляет список/массив индексов в этом месте на карте.

Если вам нужно знать, сколько дубликатов есть, например, номер 2, затем найдите его запись в таблице. Количество хранимых там индексов - это общее количество дубликатов. Чтобы найти количество дубликатов после данного экземпляра значения, просто проверьте, сколько индексов происходит после нужного индекса.

Если n - размер массива, а я - индекс элемента, то вам нужно, чтобы каждый элемент просматривал n-i-1 элементов. В результате вы сделаете n * (n - 1) сравнение элементов.

Вы можете использовать стандартный алгоритм std::count

Например

const size_t N = 5;

int a[N] = { 1, 2, 2, 3, 4 };

for ( int *first = a; first != a + N; ++first )
{
   std::cout << *first << '\t' << std::count( first, a + N, *first ) - 1 << std::endl;
} 

Или

for ( int *first = a; first != a + N; ++first )
{
   std::cout << *first << '\t' << std::count( first + 1, a + N, *first ) << std::endl;
} 

То же самое можно записать также как

for ( auto *first = std::begin( a ); first != std::end( a ); ++first )
{
   std::cout << *first << '\t' << std::count( first, std::end( a ), *first ) - 1 << std::endl;
} 

или как

for ( auto *first = std::begin( a ); first != std::end( a ); ++first )
{
   std::cout << *first << '\t' << std::count( std::next( first ), std::end( a ), *first ) << std::endl;
} 

Не знаю, был ли это самый быстрый подход, но мое предложение было бы:

• Сделайте вторичный массив с таким же количеством элементов, инициализируя их 0 с
• Проверьте дубликаты последнего элемента;
  • Отметьте второй из последнего дубликата с 1,
  • затем третий из последних с 2
  • и так далее...
• Проверьте дубликаты элементов от последнего до первого, пропустите, если элемент имеет повторяющуюся отметку, отличную от 0

Как это в C:

#include <stdio.h>
#define Length 10

int main( ) {

    int SomeNumbers[Length] = { 1, 2, 2, 3, 4, 5, 20, 9, 2, 3 };
    int DupCount[Length] = { 0 };

    for ( int i = Length - 1; i >= 0; i-- ) {
        if ( DupCount[i] == 0 ) {
            int dup = 0;
            for ( int j = i - 1; j >= 0; j-- )
                if ( SomeNumbers[i] == SomeNumbers[j] )
                    DupCount[j] = ++dup;
        }
    }

    for ( int i = 0; i < Length; i++ ) printf( "%d ", DupCount[i] );

    getchar( );
    return 0;

}