分治法——找众数
要求：
寻找整数数组的众数，如果存在多个众数，则返回权值最小的那个
第一步：
要利用分治法找众数，首先就先要使数组有序。这里，我们用C语言库中的qsort进行快排：
qsort(nums, numsSize, sizeof(int), cmp_int); //nums——给定数组 //numsSize——数组大小 //cmp_int——qsort要用到的函数指针
第二步：
开始编写分治算法，寻找众数。
函数声明：
void Find_Mode(int* nums, int begin, int end)
为了方便，我们先定义两个全局变量mode_count和mode_index来记录众数出现的次数和下标
int mode_count = 0; //记录众数出现的次数 int mode_index = 0; //记录下标
我们以下面的有序数组为例：
- 首先假设众数为数组中间的数，记其下标为
mode。
int left = begin; int right = end; int mode = (right - left) / 2 + left; //为防止整形移除，故不采用(right + left)/2的写法
- 然后，移动
left和right，确定有多少个值为nums[mode]的元素：
while (left < right && nums[left] != nums[mode]) left++; while (left < right && nums[right] != nums[mode]) right--; //这样，值为nums[mode]的元素个数为(right - left + 1)
- 当确定好
nums[mode]的个数count后，就需要比较[begin, left - 1]和[right + 1, end]这两个区间的和count的大小
- 如果
[begin, left - 1]区间的大小大于或等于count就说明该区间内可能出现出现次数更多的或者权值更小的众数。因此要继续进行递归分治。- 对于区间
[right + 1, end]同理。
if (left - begin >= right - left + 1) Find_Mode(nums, begin, left - 1); if (end - right >= right - left + 1) Find_Mode(nums, right + 1, end);
- 如果上面两个
if语句没有执行，那就说明nums[mode]出现的次数count就是最大的，那就需要和mode_count(众数出现的次数)进行比较
- 如果
count == mode_count。那就比较nums[mode]和nums[mode_index]的权值，并将众数更新为权值较小的那个，并更新mode_index- 如果
count > mode_count。那就直接让众数为nums[mode]，更新mode_count和mode_index- 如果
count < mode_cout。就不做任何修改
//right - left + 1即上文所说的count if (mode_count <= right - left + 1) { //如果二者相等，就取权值较小的 if (mode_count == right - left + 1) mode_index = nums[mode] < nums[mode_index] ? mode : mode_index; else { mode_index = mode; mode_count = right - left + 1; } }
- 函数整体即为：
int mode_count = 0; //记录众数出现的次数 int mode_index = 0; //记录下标 void Find_Mode(int* nums, int begin, int end) { int left = begin; int right = end; int mode = (right - left) / 2 + left; //移动做右指针，寻找nums[mode]（假设的众数）的出现次数 while (left < right && nums[left] != nums[mode]) left++; while (left < right && nums[right] != nums[mode]) right--; //如果左右区间的长度大于或者等于nums[mode]（假设的众数）的出现次数 //那就进行分治递归 if (left - begin >= right - left + 1) Find_Mode(nums, begin, left - 1); if (end - right >= right - left + 1) Find_Mode(nums, right + 1, end); //更新众数 if (mode_count <= right - left + 1) { //如果二者相等，就取权值较小的 if (mode_count == right - left + 1) mode_index = nums[mode] < nums[mode_index] ? mode : mode_index; else { mode_index = mode; mode_count = right - left + 1; } } }
整体代码：
#include <stdio.h> #include <stdlib.h> int mode_count = 0; //记录众数出现的次数 int mode_index = 0; //记录下标 void Find_Mode(int* nums, int begin, int end) { int left = begin; int right = end; int mode = (right - left) / 2 + left; //移动做右指针，寻找nums[mode]（假设的众数）的出现次数 while (left < right && nums[left] != nums[mode]) left++; while (left < right && nums[right] != nums[mode]) right--; //如果左右区间的长度大于或者等于nums[mode]（假设的众数）的出现次数 //那就进行分治递归 if (left - begin >= right - left + 1) Find_Mode(nums, begin, left - 1); if (end - right >= right - left + 1) Find_Mode(nums, right + 1, end); //更新众数 if (mode_count <= right - left + 1) { //如果二者相等，就取权值较小的 if (mode_count == right - left + 1) mode_index = nums[mode] < nums[mode_index] ? mode : mode_index; else { mode_index = mode; mode_count = right - left + 1; } } } //qsort需要的函数 int cmp_int(void const* num1, void const* num2) { return *(int*)num1 - *(int*)num2; } int main() { int nums[] = { 10, 4, 2, 10, 5, 8, 9, 5, 6, 1, 4, 7, 2, 1, 7, 4, 3, 1, 7, 2 }; int numsSize = sizeof(nums) / sizeof(int); qsort(nums, numsSize, sizeof(int), cmp_int); //利用快速排序排序数组，是数组升序排列 Find_Mode(nums, 0, numsSize - 1); //找众数 printf("众数为：%d\n", nums[mode_index]); return 0; }
注：本题已通过牛客网[编程题]众数验证正确性。
