在 C++ 中数组中查找出现最频繁的元素
Jinku Hu
2023年10月12日
本文将演示有关如何在数组 C++ 中查找出现最频繁的元素的多种方法。
使用 std::sort 算法与迭代法来寻找数组中最频繁的元素
在数组中查找最频繁的元素的简单方法是遍历数组的排序版本并保留元素频率的计数。在这种情况下，我们假设数组是整数序列，它们存储在 std::vector 容器中。
首先，我们需要使用 std::sort 算法对整数数组进行排序，使一次遍历足以找到最频繁的元素。注意，在迭代过程中我们需要几个变量。即，我们存储最后一次迭代中的整数以与当前元素进行比较；同样，我们在循环的每个循环中都更新最频繁的整数的值。该算法检查当前元素是否等于前一个元素，并在表达式为真时递增频率计数器。如果不为真，则检查当前频率计数是否大于到目前为止遇到的最大值，如果是，则存储最大频率计数和最频繁元素的更新值。
然后，我们修改之前的整数变量，并将当前频率重置为 1。循环结束后，还有一个 if 条件可以比较当前频率和最大频率，然后我们可以确定结果元素。
#include <iostream>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::vector;
int getMostFrequentElement(vector<int> &arr) {
if (arr.empty()) return -1;
sort(arr.begin(), arr.end());
auto last_int = arr.front();
auto most_freq_int = arr.front();
int max_freq = 0, current_freq = 0;
for (const auto &i : arr) {
if (i == last_int)
++current_freq;
else {
if (current_freq > max_freq) {
max_freq = current_freq;
most_freq_int = last_int;
}
last_int = i;
current_freq = 1;
}
}
if (current_freq > max_freq) {
max_freq = current_freq;
most_freq_int = last_int;
}
return most_freq_int;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6,
7, 8, 9, 10, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10};
int ret = getMostFrequentElement(arr);
if (ret == -1) {
perror("getMostFrequentElement");
exit(EXIT_FAILURE);
}
cout << "Most frequent element = " << ret << endl;
exit(EXIT_SUCCESS);
}
输出：
Most frequent element = 10
将 std::unordered_map 容器与 std::max_element 函数一起使用以查找数组中最频繁的元素
另外，我们可以利用 std::unordered_map 类为每个元素累积频率，然后调用 std::max_element 算法来识别具有最大值的元素。请注意，累积频率需要遍历整个数组，并且每次迭代都需要在映射中插入。在这种情况下，std::max_element 方法采用三个参数，前两个参数：范围的开始和结束说明符。第三个参数是 lambda 函数，用于比较 std::unordered_map 类型为 std::pair 的元素。最后，我们可以从返回的 max_element 对算法中返回第二项。
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::unordered_map;
using std::vector;
int getMostFrequentElement(vector<int> &arr) {
if (arr.empty()) return -1;
unordered_map<int, int> freq_count;
for (const auto &item : arr) freq_count[item]++;
auto most_freq_int = std::max_element(
freq_count.begin(), freq_count.end(),
[](const auto &x, const auto &y) { return x.second < y.second; });
return most_freq_int->first;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6,
7, 8, 9, 10, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10};
int ret = getMostFrequentElement(arr);
if (ret == -1) {
perror("getMostFrequentElement");
exit(EXIT_FAILURE);
}
cout << "Most frequent element = " << ret << endl;
exit(EXIT_SUCCESS);
}
输出：
Most frequent element = 10
作者： Jinku Hu
