Алгоритм поиска повторяющихся чисел в массиве --- Самый быстрый способ

Question

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

Например: если массив равен {2,3,4,5,2,4,6,2,4,7,3,8,2}

Я должен знать, что есть четыре 2, два 3 и три 4.

Answer 1

Существует «алгоритм», который я все время использую, чтобы найти повторяющиеся строки в файле в Unix:

sort file | uniq -d

Если вы реализуете ту же стратегию в C, то очень сложно победить ее с помощью более изящной стратегии, такой как хеш-таблицы. Вызовите алгоритм сортировки, а затем вызовите собственную функцию для обнаружения дубликатов в отсортированном списке. Алгоритм сортировки занимает время O (n * log (n)), а функция uniq - линейное время. («Южное гостеприимство» делает то же самое, но я хочу подчеркнуть, что то, что он называет «вариантом 2», кажется и проще, и быстрее, чем предложение более популярных хеш-таблиц.)

Answer 2

вариант 1: хэш Вариант 2: сортировка и подсчет последовательных прогонов.

Answer 3

Код сначала сортирует массив, а затем перемещает уникальные элементы вперед, отслеживая количество элементов. Это медленнее, чем использование сортировки по группам, но более удобно.

#include <stdio.h>
#include <stdlib.h>

static int cmpi(const void *p1, const void *p2)
{
    int i1 = *(const int *)p1;
    int i2 = *(const int *)p2;
    return (i1 > i2) - (i1 < i2);
}

size_t make_unique(int values[], size_t count, size_t *occ_nums)
{
    if(!count) return 0;

    qsort(values, count, sizeof *values, cmpi);

    size_t top = 0;
    int prev_value = values[0];
    if(occ_nums) occ_nums[0] = 1;

    size_t i = 1;
    for(; i < count; ++i)
    {
        if(values[i] != prev_value)
        {
            ++top;
            values[top] = prev_value = values[i];
            if(occ_nums) occ_nums[top] = 1;
        }
        else ++occ_nums[top];
    }

    return top + 1;
}

int main(void)
{
    int values[] = { 2, 3, 4, 5, 2, 4, 6, 2, 4, 7, 3, 8, 2 };

    size_t occ_nums[sizeof values / sizeof *values];
    size_t unique_count = make_unique(
        values, sizeof values / sizeof *values, occ_nums);

    size_t i = 0;
    for(; i < unique_count; ++i)
    {
        printf("number %i occurred %u time%s\n",
            values[i], (unsigned)occ_nums[i], occ_nums[i] > 1 ? "s": "");
    }
}

Answer 4

> I need the fastest and simple algorithm which finds the duplicate numbers in an array, also should be able to know the number of duplicates.

Я думаю, что самый быстрый алгоритм подсчитывает дубликаты в массиве:

#include <stdlib.h> 
#include <stdio.h> 
#include <limits.h> 
#include <assert.h> 

typedef int arr_t;
typedef unsigned char dup_t;
const dup_t dup_t_max=UCHAR_MAX;

dup_t *count_duplicates( arr_t *arr, arr_t min, arr_t max, size_t arr_len ){
  assert( min <= max );
  dup_t *dup = calloc( max-min+1, sizeof(dup[0]) );
  for( size_t i=0; i<arr_len; i++ ){
    assert( min <= arr[i] && arr[i] <= max && dup[ arr[i]-min ] < dup_t_max );
    dup[ arr[i]-min ]++;
  }
  return dup;
}

int main(void){
  arr_t arr[] = {2,3,4,5,2,4,6,2,4,7,3,8,2};
  size_t arr_len = sizeof(arr)/sizeof(arr[0]);
  arr_t min=0, max=16;
  dup_t *dup = count_duplicates( arr, min, max, arr_len );
  printf( "  value count\n" );
  printf( "  -----------\n" );
  for( size_t i=0; i<(size_t)(max-min+1); i++ ){
    if( dup[i] ){
      printf( "%5i %5i\n", (int)(i+min), (int)(dup[i]) );
    }
  }
  free(dup);
}

Примечание: Вы не можете использовать самый быстрый алгоритм для каждого массива.

Answer 5

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

Как пример в python:

numberList = [1, 2, 3, 2, 1, ...]
countDict = {}
for value in numberList:
    countDict[value] = countDict.get(value, 0) + 1

# Now countDict contains each value pointing to their count

Подобные конструкции существуют в большинстве языков программирования.