Найти, какие числа больше всего отображаются в векторе

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

Есть ли простой/быстрый алгоритм (STL или что-то еще), что делает это?

источник

2010-03-21 VaioIsBorn

См. Вопросы: http://stackoverflow.com/questions/1204313/counting-occurences-in-a-vector, http://stackoverflow.com/questions/2184336/how-to-get-the-most -represented-object-from-an-array – outis

Сортируйте его, затем проведите по нему и сохраните счетчик, который вы увеличиваете, когда текущий номер совпадает с предыдущим номером и в противном случае сбрасывается на 0. Также следите за тем, что было самым высоким значением счетчика до сих пор и каково текущее число, когда это значение было достигнуто. Это решение - O(n log n) (из-за сортировки).

В качестве альтернативы вы можете использовать hashmap от int до int (или если вы знаете, что числа находятся в ограниченном диапазоне, вы можете просто использовать массив) и перебирать вектор, увеличивая the_hashmap[current_number] на 1 для каждого номера. Затем итерации через хэш-карту можно найти ее наибольшее значение (и принадлежащий ему ключ). Для этого требуется структура данных hashmap (если вы не можете использовать массивы, которые также будут быстрее), что не является частью STL.

источник

2010-03-21 22:14:20 sepp2k

Просто чтобы добавить очевидное, для сортировки с использованием сортировки STL: http://www.cplusplus.com/reference/algorithm/sort/ –

@ Steve314: unordered_map будет в наступающем стандарт. Это не в 2003 году (то есть текущий) стандарт. – sepp2k

Wierd - Я как-то понял, что TR1 был «первой редакцией текста» в 2003 году. – Steve314

Это, как я сделал это:

int max=0,mostvalue=a[0]; 
    for(i=0;i<a.size();i++) 
    { 
     co = (int)count(a.begin(), a.end(), a[i]); 
     if(co > max) 
     {  max = co; 
       mostvalue = a[i]; 
     } 
    }

Я просто не знаю, как быстро это, то есть O()? Если бы кто-то мог рассчитать его и опубликовать здесь, это было бы хорошо.

источник

2010-03-21 22:25:50 VaioIsBorn

Это O (n * n), поэтому не самый эффективный метод, но он доступен только для чтения и не требует дополнительной памяти, если это важно. –

Это O (n^2), потому что каждый раз, когда вы вызываете счет, он смотрит на каждый элемент вектора. Это можно сделать в O (n) (http://stackoverflow.com/questions/512590/computing-the-statistical-mode/512601#512601) –

Если вы хотите, чтобы избежать сортировок своего вектора v используйте карту:

int max = 0; 
int most_common = -1; 
map<int,int> m; 
for (vi = v.begin(); vi != v.end(); vi++) { 
    m[*vi]++; 
    if (m[*vi] > max) { 
    max = m[*vi]; 
    most_common = *vi; 
    } 
}

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

источник

2010-03-21 22:58:10 tucuxi

Найти, какие числа больше всего отображаются в векторе

ответ

Смежные вопросы