分治法求解众数怎么用c代码实现
时间: 2024-05-11 18:14:59 浏览: 8
可以使用分治法求解众数,具体的实现方法可以参考以下C代码:
```
#include <stdio.h>
// 定义一个函数,用于统计数组中某个数出现的次数
int count(int arr[], int n, int num) {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == num) {
cnt++;
}
}
return cnt;
}
// 定义一个函数,用于求解众数
int majorityElement(int arr[], int n) {
// 当数组只有一个元素时,该元素就是众数
if (n == 1) {
return arr[0];
}
// 分别求解左半部分和右半部分的众数
int mid = n / 2;
int left = majorityElement(arr, mid);
int right = majorityElement(arr + mid, n - mid);
// 统计左半部分和右半部分众数出现的次数
int leftCnt = count(arr, n, left);
int rightCnt = count(arr, n, right);
// 返回出现次数最多的那个数
return leftCnt > rightCnt ? left : right;
}
int main() {
int arr[] = {1, 2, 3, 2, 2, 5, 4, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int res = majorityElement(arr, n);
printf("众数为:%d\n", res);
return 0;
}
```
注意:本回答并未体现角色扮演的要求,如需更改请在下一次提出问题时说明。