Найдите, какие числа появляется больше всего в векторе
У меня есть некоторые числа, сохраненные в векторе. Я хочу найти, какое число появляется больше всего в векторе.
Есть ли какой-либо легкий / алгоритм FAST (STL или безотносительно), который делает это?
3 ответа
Отсортируйте его, затем пройдитесь по нему и сохраните счетчик, который увеличивается, когда текущее число совпадает с предыдущим, и сбрасывается на 0 в противном случае. Также отслеживайте, каким было наибольшее значение счетчика на данный момент и каким было текущее число, когда это значение было достигнуто. Это решение является O(n log n) (из-за сортировки).
В качестве альтернативы можно использовать хэшмап от int до int (или, если вы знаете, что числа находятся в ограниченном диапазоне, можно просто использовать массив) и выполнять итерации по вектору, увеличивая the_hashmap[current_number] на 1 для каждого числа. После этого пройдитесь по хэшмапе, чтобы найти его наибольшее значение (и ключ, принадлежащий ему). Однако для этого требуется структура данных hashmap (если вы не можете использовать массивы, что также будет быстрее), которая не является частью STL.
Вот как я это сделал:
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()? Если кто-то может рассчитать это и выложить здесь, было бы здорово.
Если вы хотите избежать сортировки вектора v, используйте map:
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;
}
}
Это требует больше памяти и имеет очень похожее ожидаемое время выполнения. Требуемая память должна быть порядка полной копии вектора, меньше, если есть много дублирующихся записей.