C++ で配列の最も頻繁な要素を検索する
-
配列内で
std::sortアルゴリズムと反復法を使用して最も頻繁な要素を検索する -
配列内で
std::unordered_mapコンテナとstd::max_element関数を使用して最も頻繁な要素を検索する
この記事では、配列 C++ で最も頻繁に使用される要素を見つける方法に関する複数の方法を示します。
配列内で std::sort アルゴリズムと反復法を使用して最も頻繁な要素を検索する
配列内で最も頻繁な要素を見つけるための簡単な解決策は、配列のソートされたバージョンをトラバースし、要素の頻度のカウントを保持することです。この場合、配列は整数のシーケンスであり、std::vector コンテナに格納されていると想定しています。
最初に、std::sort アルゴリズムを使用して整数の配列を並べ替える必要があります。これにより、最も頻繁な要素を見つけるのに 1 回の走査で十分になります。反復中にいくつかの変数が必要であることに注意してください。つまり、現在の要素と比較するために、最後の反復からの整数を格納します。また、ループの各サイクルで最も頻繁に更新される整数の値を保持します。アルゴリズムは、現在の要素が前の要素と等しいかどうかを確認し、式が true の場合に周波数カウンターをインクリメントします。true でない場合、現在の頻度カウントがこれまでに検出された最大値より大きいかどうかを確認し、大きい場合は、最大頻度カウントと最も頻度の高い要素の更新された値を保存します。
次に、前の整数変数を変更し、現在の周波数を 1 にリセットします。ループが終了すると、現在の周波数と最大周波数を比較するためのもう 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 メソッドは 3つの引数を取り、最初の 2つは範囲の開始指定子と終了指定子です。3 番目の引数は、タイプ std::pair の std::unordered_map の要素を比較するラムダ関数です。最後に、返されたペア max_element アルゴリズムから 2 番目のアイテムを返すことができます。
#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
