Максимум вхождений
Я хочу найти элемент в массиве, который имеет максимальное количество вхождений и знаю количество вхождений. Пожалуйста, предложите мне самый быстрый код C ++ для этого (вы можете использовать STL, если это может помочь).
Решение
Вы можете иметь O(n log n) Решение этой проблемы в C ++.
Сначала используйте O(n log n) Сортировать (Сортировка кучи, Сортировка слиянием, Быстрая сортировка, и т. д.) для сортировки количества элементов в списке. Если вас не волнует сложность алгоритма, отсортируйте список, используя Bubble Sort, В этом случае сложность алгоритма станет На2).
Затем используйте следующий код, который принимает O(n) время, чтобы найти элемент с наибольшим вхождением из отсортированного списка.
maxfreq=0;
freq=1;
for(i=0;i<(MAX-1);i++)
{
if(list[i]==list[i+1])
{
freq++;
if(freq > maxfreq)
{
maxfreq=freq;
maxind=i;
}
}
else
{
freq=1;
}
}
cout<<"Element "<<list[maxind]<<" occurs "<<maxfreq<<" times in the list";
Общее время O(log n + n), Таким образом, сложность алгоритма O(log n),
Другие решения
Вот один из способов сделать это в C ++ 11:
#include <vector>
#include <map>
int most_frequent_element(std::vector<int> const& v)
{ // Precondition: v is not empty
std::map<int, int> frequencyMap;
int maxFrequency = 0;
int mostFrequentElement = 0;
for (int x : v)
{
int f = ++frequencyMap[x];
if (f > maxFrequency)
{
maxFrequency = f;
mostFrequentElement = x;
}
}
return mostFrequentElement;
}
Вы можете использовать вышеуказанную функцию следующим образом:
#include <iostream>
int main()
{
std::vector<int> v { 1, 3, 5, 6, 6, 2, 3, 4, 3, 5 };
std::cout << most_frequent_element(v);
}
Вот живой пример.
С незначительной модификацией вышеупомянутая функция может быть обобщена для работы с любым контейнером (не только std::vector):
template<typename T>
typename T::value_type most_frequent_element(T const& v)
{ // Precondition: v is not empty
std::map<typename T::value_type, int> frequencyMap;
int maxFrequency = 0;
typename T::value_type mostFrequentElement{};
for (auto&& x : v)
{
int f = ++frequencyMap[x];
if (f > maxFrequency)
{
maxFrequency = f;
mostFrequentElement = x;
}
}
return mostFrequentElement;
}
Благодаря выводу типа шаблона вы бы вызвали вышеуказанный шаблон функции точно так же, как и исходный.
Вот живой пример.
Кроме того, для еще большей производительности вы можете рассмотреть возможность использования C ++ 11 std::unordered_map скорее, чем std::map, std::unordered_map дает вам сложность O (1) для вставки и поиска. Я оставлю его использование в приведенных выше примерах на ваше усмотрение.