众数问题分治法c语言
时间: 2024-03-23 09:35:01 浏览: 162
众数问题是指在一个给定的数组中,出现次数最多的元素称为众数。分治法是一种解决问题的思想,它将问题分解成更小的子问题,并通过合并子问题的解来得到原问题的解。下面是使用分治法解决众数问题的C语言代码示例:
```c
#include <stdio.h>
// 求解众数的函数
int majorityElement(int nums[], int left, int right) {
// 当只有一个元素时,直接返回该元素
if (left == right) {
return nums[left];
}
// 分别求解左右子数组的众数
int mid = (left + right) / 2;
int leftMajority = majorityElement(nums, left, mid);
int rightMajority = majorityElement(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 main() {
int nums[] = {1, 2, 2, 2, 3, 4, 2};
int n = sizeof(nums) / sizeof(nums[0]);
int result = majorityElement(nums, 0, n - 1);
printf("The majority element is: %d\n", result);
return 0;
}
```
上述代码中,`majorityElement`函数使用递归的方式将数组分解成更小的子数组,并分别求解左右子数组的众数。然后通过统计左右子数组中众数出现的次数,返回出现次数较多的众数。在`main`函数中,我们定义了一个示例数组`nums`,并调用`majorityElement`函数来求解众数。最后将结果打印输出。
阅读全文