Определение того, как часто каждый элемент появляется в массиве?

Question

Существует эффективный алгоритм C, чтобы вычислить и сообщить количество одинаковых элементов в массиве

Например, если мы имеем

int Z[] = { 4, 9, 4, 10, 4, 2, 10, 1, 19, 21, 21 }; 

, то результат должен быть

elem   number 
    4   3 
    9   1 
    10   2 
    2   1 
    1   1 
    19   1 
    21   2 

Answer 1

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

Во-первых, вы можете просто выполнить двойной цикл над массивом и для каждого элемента подсчитать, сколько раз оно появляется. Это займет время O (n), где n - количество элементов массива. Однако для этого требуется только пространство O (1).

Во-вторых, вы можете отсортировать массив в порядке возрастания, который будет группировать одинаковые элементы. Оттуда легко увидеть, сколько раз каждый элемент появляется, поскольку вы можете перебирать массив по одному и подсчитывать, сколько раз подряд появляется каждый элемент. Используемое время выполнения и пространство зависят от того, как вы сортируете массив. Если вы используете heapsort, время выполнения будет O (n log n), а использование пространства будет только O (1). Если вам известны все элементы в диапазоне массивов от 0 до U включительно, вы можете использовать сортировку подсчета во времени O (n + U) и пробел O (U) или сортировку по методу Radix во времени O (n log U) и пробел На).

В-третьих, вы можете создать вспомогательную таблицу, в которой хранятся частоты каждого элемента, и заполнить ее, итерации по массиву один раз, заполняя записи по мере их поступления. Если вы используете хэш-таблицу, ожидаемая продолжительность выполнения будет O (n), а использование пространства будет равно O (n). Если вы знаете, что элементы массива находятся в диапазоне от 0 до U, включительно, вы можете просто использовать частотный массив и решить это во времени O (n + U) и пространстве O (U) (что, по сути, будет считаться сортировкой!)

Здесь нет явного победителя. У Heapsort лучшая временная сложность для использования O (1). Хешинг имеет лучшую общую временную сложность, но плохое использование пространства. Подсчет или сортировка по методу radix может быть лучше всего в зависимости от того, насколько велики цифры.

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

Answer 2

Вот ответ, который работает.

Первый цикл инициализирует массив чисел чисел для всех нулей.

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

Наконец, третий цикл просто проходит через массив чисел и печатает результаты в удобном порядке.

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

#include <stdlib.h> 
    #include <stdio.h> 
    int main(){ 
     int Z[] = { 4, 9, 4, 10, 4, 2, 10, 1, 19, 21, 21, 0}; 
     int n; 
     int lowest=1; 
     int highest=100; 
     int counts[highest+1]; 
     for (n=0;n<=highest;n++){ 
     counts[n]=0; 
     } 
     int *num=Z; 
     while((int)*num != 0){ 
     counts[*num]++; 
     num++; 
     } 

     for (n=lowest;n<=highest;n++){ 
     if (counts[n] > 0){ 
      printf("%d = %d\n",n,counts[n]); 
     } 
     } 
     return 0; 
    }