C++分治法求数组中最多的数
时间: 2024-06-01 19:10:38 浏览: 22
题目描述:
给定一个长度为n的数组,找出出现次数最多的数,如果有多个,输出任意一个即可。
算法思路:
采用分治法的思想,将数组不断划分为左右两个子区间,分别求出左子区间和右子区间出现次数最多的数,然后比较两个数的出现次数,取较大值作为当前区间的出现次数最多的数。
具体实现:
对于一个区间[l, r],如果l=r,则该区间只有一个数,直接返回该数即可。
否则,将区间[l, r]划分为两个子区间[l, mid]和[mid+1, r],分别递归求解左子区间和右子区间出现次数最多的数。
然后统计左子区间和右子区间出现次数最多的数的个数,比较两个数的出现次数,取较大值作为当前区间的出现次数最多的数。
最后返回当前区间的出现次数最多的数即可。
代码实现:
int a[MAXN]; // 数组a
int cnt[MAXN]; // 统计每个数出现的次数
int n; // 数组长度
// 求区间[l, r]中出现次数最多的数
int solve(int l, int r) {
if (l == r) return a[l]; // 如果区间只有一个数,直接返回该数
int mid = (l + r) >> 1; // 将区间划分为两个子区间[l, mid]和[mid+1, r]
int x = solve(l, mid); // 递归求解左子区间的出现次数最多的数
int y = solve(mid+1, r); // 递归求解右子区间的出现次数最多的数
int cnt_x = 0, cnt_y = 0; // 统计左子区间和右子区间出现次数最多的数的个数
for (int i = l; i <= r; i++) {
if (a[i] == x) cnt_x++; // 统计x的个数
else if (a[i] == y) cnt_y++; // 统计y的个数
}
if (cnt_x > cnt_y) return x; // 如果x的个数比y的个数多,返回x
else return y; // 否则返回y
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
cnt[a[i]]++; // 统计每个数出现的次数
}
int ans = 0, max_cnt = 0; // ans表示出现次数最多的数,max_cnt表示出现次数最多的数的次数
for (int i = 1; i <= n; i++) {
if (cnt[a[i]] > max_cnt) { // 如果a[i]出现的次数比当前出现次数最多的数的次数还要多
ans = a[i]; // 更新出现次数最多的数
max_cnt = cnt[a[i]]; // 更新出现次数最多的数的次数
}
}
printf("%d\n", ans); // 输出出现次数最多的数
return 0;
}
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![](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)