как работает std :: map для подсчета дубликатов - PullRequest
Новая
       30

как работает std :: map для подсчета дубликатов

0 голосов
/ 30 апреля 2020

Я новичок в cp, и недавно я наткнулся на проблему , которую я не смог решить с помощью вектора, поэтому я проверил решение и увидел, что в большинстве кодов была карта , Может кто-нибудь объяснить, как std :: map работает в этой конкретной проблеме. Это одно из следующих решений: 

int main()
{
    int n,mx=0,cnt=0,i,x;
    cin>>n;
    map<int,int>mp;
    for(i=0;i<n;i++)
    {
      cin>>x;
      mp[x]++;
      if(mp[x]>mx)
      {
        mx=mp[x];
      }
    }
    cout<<mx<<endl;
    return 0;
}

Ответы [ 2 ]

1 голос
/ 30 апреля 2020

std::map - это структура, которая связывает одно значение с одним уникальным ключом.

Эффект net в том, что каждый отдельный ключ может иметь только одно значение.

в случае map<int, int> mp значение, связанное с mp[123], представляет собой одно целое число. В картах C ++ автоматически создаются несуществующие элементы, поэтому при первом доступе значение, связанное с mp[123], будет инициализировано значением 0, и вы можете спокойно считать, используя mp[x]++.

Сказав, что с помощью клавиш int тот же эффект может быть достигнут с помощью простого массива. Если ключ плотный и максимальное значение ключа известно, вы можете просто выделить массив (вектор) и использовать ключ в качестве индекса в нем. Карта полезна, когда ключи редкие, не нумеруются c, или когда диапазон неизвестен.

В вашем конкретном случае диапазон клавиш, как представляется, [1 ... 100]. Это можно решить с помощью массива. Карта не нужна. 

int main()
{
    int n, mx = 0, x;
    cin >> n;
    int mp[101]{};
    for (int i = 0; i < n; i++)
    {
        cin >> x; // 1 <= x <= 100 according to problem definition
        mx = max(mx, ++mp[x]);
    }
    cout << mx << endl;
    return 0;
}
0 голосов
/ 30 апреля 2020

mp - это счетчик того, сколько раз каждое число было замечено во входных данных. Это последовательность пар чисел, причем первое («ключ») берется из входа, а второе («значение») - счет. В этой программе нам все равно, но эти пары упорядочены по ключу.

Каждый раз, когда вокруг l oop, mp[x]++; добавляет единицу к счету для числа x. Если число раньше не было видно, оно увеличивается от 0 до 1, потому что 0 - это значение инициализированной по умолчанию int.

. Тогда mx устанавливается на большее из себя и обновленное число для x.

...