Как можно улучшить данный код?

Question

[Jepa]

На телевизионном шоу зрители голосуют за участников шоу, отправляя SMS-сообщение с номером участника. Определите победителя шоу на основе присланных SMS-сообщений.

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

int n;
    cin >> n;
    int mxind = 0;
    int mxx = 0;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if(tmp > mxx)
        {
            a.resize(tmp+1);
            mxx = tmp;
        }
        if(tmp > mxind)
            mxind = tmp;
        a[tmp]++;
    }
    int mx = *max_element(a.begin(), a.end());
    for(int i = 0; i < mxind+3; i++)
    {
        if(a[i] == mx)
            cout << i << " ";
    }

Comments

[mayton2019]

Весь код давай.

[Василий Банников]

1. Зачем ты так шифруешь имена переменных? Что значит "mxind", "mxx", "tmp", "a", "n"?
2. Без условий задачи хз, как именно можно оптимизировать код, но по формулировке могу предположить, что тебе скорее hashmap нужен, чем vector
3. Какое максимальное значение?

[Jepa]

mayton2019,

На телевизионном шоу зрители голосуют за участников шоу, отправляя SMS-сообщение с номером участника. Определите победителя шоу на основе присланных SMS-сообщений.

Входные данные
Первая строка входных данных содержит количество присланных сообщений 1 ≤ N ≤ 104. Во второй строке содержится натуральных N чисел - список номеров, присланных телезрителями, через пробел. Все числа не превосходят 109.

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

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    vector<int> a(100001, 0);
    int n;
    cin >> n;
    int mxind = 0;
    int mxx = 0;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        if(tmp > mxx)
        {
            a.resize(tmp+1);
            mxx = tmp;
        }
        if(tmp > mxind)
            mxind = tmp;
        a[tmp]++;
    }
    int mx = *max_element(a.begin(), a.end());
    for(int i = 0; i < mxind+3; i++)
    {
        if(a[i] == mx)
            cout << i << " ";
    }
}
int main()
{
    solve();
}

[Jepa]

Василий Банников, 1. mxind это максимальный индекс элемента чтобы не нужно было по все огромному массиву идти.
3. 10^9

[mayton2019]

Jepa, да тут как-то слишком сложно написано. Зачем vector?
Тут вот так надо

std::map<int, int> mobileVotes;
.... добавляем голоса. Наращиваем счетчик value.
....
// сортируем по счетчику сообщений
// печатаем результат

[Василий Банников]

Jepa, Это максимальный номер, максимальное количество голосов за одного кандидата, максимальное количество кандидатов, или максимальное количество голосов вообще?

[Jepa]

mayton2019, А как сортировать мап? Просто я не очень хорошо его знаю.
И ещё, добавление голоса делаем так:

int tmp;
cin >> tmp;
mp[tmp]++;

?

[Jepa]

Василий Банников, максимальный номер 10**9, максимальное количество голосов тоже 10**9, максимальное количество голосов вообще 10**4

[Василий Банников]

Jepa, тогда сделай map<int64_t, int64_t> и всё будет легко решаться.

[Василий Банников]

Jepa, что такое tmp у тебя?

[Jepa]

Василий Банников, это число которое вводит пользователь ну или же его голос

[Василий Банников]

Jepa, почему тогда это называется tmp, а не vote?

[mayton2019]

Jepa,

А как сортировать мап? Просто я не очень хорошо его знаю

Тут - хитрость. Тебе вобщем-то не надо его сортировать. Тебе надо найти max из всей коллекции (мапы).
Напечатать его на экране. И еще по заданию написано что надо сделать поиск таких-же максималов.
Поэтому удаляем из мапы счастливчика и просто повторяем поиск max. И так далее пока количество голосов
совпадает.

Впрочем при случайном распределении голосов это маловероятно. Скорее всего счастливчик будет один.
И в тестовых кейсах возможно 2 или 3.

Если эти редкие кейсы все таки будут в тестировании твоего исходника - то возможно будет фейл по времени.
Тогда план Б - конвертить в heap. Где-то даже процедура такая есть хипи-зация. Heapyfy. Или makeHeap.
Она из коллекции делает квази-сортированный массив (куча или пирамида). И из него можно брать 2-3 счастливчика. Сохраняя свойство пирамиды.

Answer 1

[Василий Банников]

1. используй std::map для хранения количества голосов за каждого кандидата и int64_t для хранения номера кандидата.
2. Вот что первым выдаёт гугл на запрос "как найти элемент с максимальным value в std::map C++":
https://www.techiedelight.com/find-element-with-th...