在 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
