C++ 实现简单多数法

以下是几种用 C++ 实现简单多数法的代码示例：

暴力遍历法

收起

cpp

#include <iostream>
#include <vector>char majorityElementBruteForce(const std::vector<char>& grades) {int n = grades.size();for (int i = 0; i < n; ++i) {int count = 0;for (int j = 0; j < n; ++j) {if (grades[i] == grades[j]) {count++;}}if (count > n / 2) {return grades[i];}}return '\0'; // 表示没有多数元素
}int main() {std::vector<char> grades = { 'a', 'b', 'a', 'c', 'a', 'a', 'd' };char result = majorityElementBruteForce(grades);if (result!= '\0') {std::cout << "多数成绩等级是: " << result << std::endl;} else {std::cout << "没有多数成绩等级" << std::endl;}return 0;
}

哈希表法

收起

cpp

#include <iostream>
#include <vector>
#include <unordered_map>char majorityElementHashTable(const std::vector<char>& grades) {std::unordered_map<char, int> gradeCount;int n = grades.size();for (char grade : grades) {gradeCount[grade]++;if (gradeCount[grade] > n / 2) {return grade;}}return '\0'; // 表示没有多数元素
}int main() {std::vector<char> grades = { 'a', 'b', 'a', 'c', 'a', 'a', 'd' };char result = majorityElementHashTable(grades);if (result!= '\0') {std::cout << "多数成绩等级是: " << result << std::endl;} else {std::cout << "没有多数成绩等级" << std::endl;}return 0;
}

摩尔投票法

收起

cpp

#include <iostream>
#include <vector>char majorityElementBoyerMoore(const std::vector<char>& grades) {char candidate = '\0';int count = 0;for (char grade : grades) {if (count == 0) {candidate = grade;count = 1;} else if (grade == candidate) {count++;} else {count--;}}// 验证候选元素是否真的是多数元素count = 0;for (char grade : grades) {if (grade == candidate) {count++;}}if (count > grades.size() / 2) {return candidate;} else {return '\0'; // 表示没有多数元素}
}int main() {std::vector<char> grades = { 'a', 'b', 'a', 'c', 'a', 'a', 'd' };char result = majorityElementBoyerMoore(grades);if (result!= '\0') {std::cout << "多数成绩等级是: " << result << std::endl;} else {std::cout << "没有多数成绩等级" << std::endl;}return 0;
}

qstring majorityElementHashTable(const std::vector<qstring >& grades) 参数改成这个试试

以下是将参数修改为const std::vector<QString >& grades（假设你这里是使用 Qt 框架中的QString类型，需要包含<QString>头文件并且正确配置好 Qt 相关环境才能编译通过）的使用哈希表来实现简单多数法的 C++ 代码示例，示例代码如下：

收起

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <QString>// 这里使用QString类型的版本
QString majorityElementHashTable(const std::vector<QString>& grades) {std::unordered_map<QString, int> gradeCount;int n = grades.size();for (const QString& grade : grades) {gradeCount[grade]++;if (gradeCount[grade] > n / 2) {return grade;}}return QString();  // 返回空的QString表示没有多数元素
}int main() {std::vector<QString> grades = { QString("a"), QString("b"), QString("a"), QString("c"), QString("a"), QString("a"), QString("d") };QString result = majorityElementHashTable(grades);if (!result.isEmpty()) {std::cout << "多数成绩等级是: " << result.toStdString() << std::endl;}else {std::cout << "没有多数成绩等级" << std::endl;}return 0;
}

在上述代码中：

majorityElementHashTable函数接受一个std::vector<QString>类型的参数grades，表示成绩等级的集合。
在函数内部，通过std::unordered_map<QString, int>来统计每个不同的QString类型成绩等级出现的次数，每遍历一个成绩等级，就在对应的计数器上加 1，一旦某个成绩等级的计数超过了总元素个数的一半，就直接返回该成绩等级作为多数元素。
在main函数中，创建了一个包含QString类型元素的vector来模拟成绩等级数据，并调用majorityElementHashTable函数获取结果，根据结果是否为空来输出相应的提示信息。