выбор элемента с большим количеством дубликатов в массиве в простом C

Question

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

В основном у меня есть массив из 256 элементов,в массиве может быть 1 элемент, 14 или 256. Этот массив содержит имена пользователей, запрашивающих данные из системы.Я пытаюсь посчитать дубликаты в списке, чтобы я мог отдать приоритет пользователю с большинством запросов.Итак, если бы у меня был список, такой как:

{john, john, paul, james, john, david, charles, charles, paul, john}

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

Я уверен, что есть простой способ сделать это.Есть идеи?Код был бы очень полезен здесь.Спасибо!

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

Буфер объявлен как:

static WCHAR userbuffer[150][128];

Может быть до 150 пользователей и каждое имя пользователя длиной до 128 символов.

Answer 1

1 - сортировка вашего массива.

2 - установить maxcount = 0;

3 - перебрать массив и считать до имени пользователя visitNEXT.

4 - если count> maxcount, тогда установить maxcount для подсчета и сохранить имя каккандидат.

5 - после завершения цикла забрать кандидата.

Answer 2

Вот как бы я решил это:

Сначала определите структуру для хранения имен пользователей и счетчиков частоты и создайте их массив с тем же количеством элементов, что и в вашем массиве userbuffer (в вашем примере 150).

struct user {
    WCHAR   name[128];
    int     count;
} users[150];

Теперь переберите userbuffer и для каждой записи проверьте и посмотрите, есть ли у вас запись в users, которая имеет тот же name. Если вы найдете совпадение, увеличьте count для этой записи в users. Если вы не нашли соответствия, скопируйте имя пользователя из userbuffer в пустую запись в users и установите для этого пользователя count значение 1.

После обработки всего массива userbuffer вы можете использовать значения count из массива users, чтобы узнать, у кого больше всего запросов. Вы можете либо пройти по нему вручную, чтобы найти максимальное значение, либо использовать qsort.

Это не самый эффективный алгоритм, но он прямой и не делает ничего слишком умного или причудливого.

Edit: Чтобы qsort массив users, вам нужно определить простую функцию, которую qsort может использовать для сортировки. Для этого примера примерно так должно работать:

static int compare_users(const void *p1, const void *p2) {
    struct user *u1 = (struct user*)p1;
    struct user *u2 = (struct user*)p2;

    if (u1->count > u2->count)
        return 1;
    if (u1->count < u2->count)
        return -1;
    return 0;
}

Теперь вы можете передать эту функцию qsort, например:

qsort(users, 150, sizeof(struct user), compare_users);

Answer 3

Что вы имели в виду под "может быть 1 элемент в массиве, 14 или 256".Есть 14 и 256 номеров элементов?

Если вы можете изменить определение массива, я думаю, что лучший способ будет определить структуру с двумя полями, username и numberOfRequests.Когда пользователь запрашивает, если в списке есть имена пользователей, числоOfRequest будет увеличено.Если это первый раз, когда пользователь запрашивает имя пользователя, его следует добавить в список, а numberOfRequests будет равно 1.

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

Однако, возможно, есть библиотека с такой функциональностью, но я сомневаюсь, что вы можете найти что-то в стандартной библиотеке!

Answer 4

Используя std :: map в соответствии с предложением AraK, вы можете хранить свои имена без дубликатов и связывать свои имена со значением.

Быстрый пример:

std::map<string, long> names;

names["john"]++;
names["david"]++;

Затем вы можете искать, какой ключ имеет наибольшее значение.