众数问题(分治法)c++
时间: 2024-06-15 08:05:14 浏览: 17
众数问题是指在一个给定的数组中,找出出现次数最多的元素。分治法是一种解决众数问题的常用方法。下面是使用分治法解决众数问题的C++代码示例:
```cpp
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int findMajorityElement(vector<int>& nums, int left, int right) {
// 如果只有一个元素,则它就是众数
if (left == right) {
return nums[left];
}
// 分别找出左半部分和右半部分的众数
int mid = left + (right - left) / 2;
int leftMajority = findMajorityElement(nums, left, mid);
int rightMajority = findMajorityElement(nums, mid + 1, right);
// 如果左右两部分的众数相同,则直接返回
if (leftMajority == rightMajority) {
return leftMajority;
}
// 统计左右两部分的众数出现次数
int leftCount = 0, rightCount = 0;
for (int i = left; i <= right; i++) {
if (nums[i] == leftMajority) {
leftCount++;
} else if (nums[i] == rightMajority) {
rightCount++;
}
}
// 返回出现次数较多的众数
return leftCount > rightCount ? leftMajority : rightMajority;
}
int majorityElement(vector<int>& nums) {
return findMajorityElement(nums, 0, nums.size() - 1);
}
int main() {
vector<int> nums = {1, 2, 2, 2, 3};
int majority = majorityElement(nums);
cout << "The majority element is: " << majority << endl;
return 0;
}
```
上述代码中,`findMajorityElement`函数使用递归的方式将数组分为左右两部分,并分别找出左右两部分的众数。然后统计左右两部分的众数出现次数,最后返回出现次数较多的众数。`majorityElement`函数是对`findMajorityElement`函数的调用,用于处理整个数组。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)