Найти число в массиве, которое встречалось чаще всего

Question

Учитывая целочисленный массив, мне нужно найти, какое число встречалось чаще всего. Я написал алгоритм, как показано ниже.

1. Используйте карту для хранения номера и количества раз, когда это произошло.

   map<int, int>

   Ключ: представляет число
   значение: представляет количество раз, когда ключ произошел.

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

Я реализовал алгоритм, как показано ниже.

#include <iostream> 
#include <map>
using namespace std; 
int main()
{
    int a[10] = {1,2,3,2,1,3,2,4,1,1}; //Input array: hardcoded for testing
    map<int, int> m;

    for(int i=0;i<10;i++)
    {
        m[a[i]]++;  //Increment the value of key for counting occurances
    }

    int mostNumTimes = 0; 
    int number = -999; //-999 represents invalid number
    map<int,int>::iterator it = m.begin();
    for( ;it != m.end(); it++)  //Find the number which occurred 
    {                           //most number of times
        if(it->second > mostNumTimes)
        {
            mostNumTimes = it->second;
            number = it->first;
        }
    }
    if(number != -999)   //Print number and number of times it occurred
    {
        cout<<"Number: "<<number<<endl;
        cout<<"Number of times occured: "<<mostNumTimes<<endl;
    }
    else
    {
        cout<<"Input array is empty"<<endl;
    }
    return 0;
}

Выход:

Номер: 1

Количество случаев: 4

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

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

Answer 1

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

map<int, int> m;
int currentMax = -999;
int maxCount = 0;
for(int i=0;i<10;i++)
{
    int updated = m[a[i]]++;  //Increment the value of key for counting occurances        
    updated++; // due to post increment 
    if (maxCount < updated) {
         maxCount = updated;
         currentMax = i;
    }
}

Поскольку это занимательное упражнение, кажется, мы все предполагаем, что итерация карты обходится дешево. Хотя итерация карты также является O (N), это намного дороже, чем итерация по вектору или массиву. Так что же дешевле, итерация карты с возможно меньшим размером или выполнение простой проверки, которая вызовет два назначения с некоторым процентом? И ваше решение, и это - O (N), при условии, что вы изменили использование неупорядоченной карты. Прямо сейчас это не так, поэтому каждая вставка - это log (n), и на самом деле я думаю, что переключение на неупорядоченную карту будет вашим самым большим выигрышем на данный момент.

Answer 2

Ваш алгоритм довольно хорош.На самом деле это O (N Log N) из-за вставок N std :: map (древовидная карта), которые вы выполняете (Log N каждый).Это доминирует во временной сложности алгоритма, так как вторая фаза является линейной.

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

Answer 3

Сортируйте массив так, чтобы вы получили ...

{1,1,1,1,2,2,2,3,3,4,4}

Затем установите переменную currentValue, и, если значение не совпадает, установите его, когда оно увеличится, увеличьте счетчик ... т.е.

currentValue = 0;
currentCount = 0;
maxValue = 0;
maxCount = 0;

for(int value in array) {
  if(currentValue == value) {
    currentCount++;
  } else {
    // is this greater than max count
    if(currentCount > maxCount) {
      maxCount = currentCount;
      maxValue = currentValue;
    }

    // reset values
    currentValue = value;
    currentCount = 0;
  }
}

Теперь у вас есть значение, которое чаще всего встречается в maxValue, и количество раз, когда оно встречалось в maxCount.

Answer 4

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

int i = 0;
int j = sizeof(a)/sizeof(int);
for(;i < j;i++, j--)
{
  if (a[i] == a[j])
  {
    update<map_t, 2>(m, a[i]);
  }
  else
  {
    update<map_t, 1>(m, a[i]);
    update<map_t, 1>(m, a[j]);
  }
}
// if array size is odd...
if (i == j)
    update<map_t, 1>(m, a[i]);

здесь обновление - простая функция, потому что мне лень набирать один и тот же код ...

template <typename M, int DEF>
void update(M& m, int v)
{
  typename M::iterator it = m.find(v);
  if (it != m.end())
      it->second += DEF;
  else
  {
    m.insert(pair<int, int>(v, DEF));
  }
}

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

Answer 5

Во-первых, вы должны избавиться от неверного номера -999. Просто спросите map.empty (), прежде чем продолжить.

Тогда, я думаю, недопустимо увеличивать элементы на карте, которых раньше не было. Я предполагаю, что новый член создается с унифицированным (случайным) значением, так как для int нет конструктора по умолчанию.

Вы можете сделать что-то еще:

map<int, int>::iterator it = m.find(i);
if (it != m.end())
    m.second++;
    if (m.second > mostTimes) {
      // reset mostTimes and maxNumber = m.first here
    }
} else {
    m[i] = 1;
}

Эта операция O (n) и, следовательно, имеет тот же класс сложности времени, что и итерация по карте снова, чтобы найти элемент max (где в худшем случае все входные числа различны, и карта будет иметь одинаковое количество членов, чем входной массив). Разница, однако, заключается в том, что большинство значений TimeM и MaxNumbers могут перезаписываться много раз, и может случиться так, что они не вписываются в регистры ЦП и происходит много обращений к ОЗУ. Так что, вероятно, выполнение итерации впоследствии будет быстрее на практике.