44 lines
977 B
C++
44 lines
977 B
C++
// 主元素寻找
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
int findMajorityElement(const vector<int>& nums) {
|
|
int candidate = -1;
|
|
int count = 0;
|
|
|
|
// 第一次遍历：找出候选主元素
|
|
for (int num : nums) {
|
|
if (count == 0) {
|
|
candidate = num;
|
|
}
|
|
count += (num == candidate) ? 1 : -1;
|
|
}
|
|
|
|
// 第二次遍历：验证候选主元素
|
|
count = 0;
|
|
for (int num : nums) {
|
|
if (num == candidate) {
|
|
count++;
|
|
}
|
|
}
|
|
|
|
// 如果候选元素出现次数超过数组长度的一半，则为所求主元素
|
|
if (count > nums.size() / 2) {
|
|
return candidate;
|
|
} else {
|
|
return -1;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
vector<int> nums = {0, 5, 3, 5, 5, 7, 5, 5};
|
|
int result = findMajorityElement(nums);
|
|
if (result != -1) {
|
|
cout << "主元素是: " << result << endl;
|
|
} else {
|
|
cout << "没有主元素" << endl;
|
|
}
|
|
return 0;
|
|
} |