先说一下题目吧，很简单，就是给一组数组，求数组中的众数，但是要用分治法。
看到这个题目还是比较迷的，求一个众数，用什么分治啊。最后参考了一下往上的各种答案，发现可以用快排的分割算法，思路如下：
首先是要运用快排的分割算法，设函数名为quick，重复次数设置为n,众数设为mode，数组长度即为length.
选取中间的值作为基准值来进行快排分割，这样做可以尽量去避免重复的计算。记k为快排分割的返回值，即为基准值的最终位置，同时在进行快排分割函数的时候需要记录基准值的重复次数，如果大于n,那么将mode更新为基准值，同时更新n.如果k-left>=n,那么左边的数可能存在众数，对数组(left,k-1)进行快排分割如果right-k>=n,那么右边的数可能存在众数，对数组(k+1,right)进行快排分割递归的去重复上述步骤。C++实现的代码如下：
#include<iostream> using namespace std; //全局变量存储重数 int n = 0; //全局变量存储众数 int mode = INT_MIN; void Swap(int* arr, int num1, int num2) { int temp = arr[num1]; arr[num1] = arr[num2]; arr[num2] = temp; } //快排分割函数 int quick(int* arr, int low, int high) { int nTemp = 1; //从中间选取基准 int mid = (low + high) / 2; if (arr[low] > arr[mid]) Swap(arr, low, mid); if (arr[low] > arr[high]) Swap(arr, low, high); if (arr[mid] > arr[high]) Swap(arr, mid, high); Swap(arr, low, mid); int temp = arr[low]; while (low < high) { while (low < high ) { if (temp == arr[high]) ++nTemp; if (temp > arr[high]) break; --high; } if (low < high) { arr[low] = arr[high]; ++low; } while (low < high ) { if (temp == arr[low]) ++nTemp; if (temp < arr[low]) break; ++low; } if (low < high) { arr[high] = arr[low]; --high; } } arr[high] = temp; if (nTemp > n) { n = nTemp; mode = temp; } return low; } void getMode(int* arr, int start, int end) { if (start >= end) return; int k = quick(arr, start, end); if ((k - start) >= n) getMode(arr, start, k - 1); if ((end - k) >= n) getMode(arr, k + 1, end); } int main() { int arr[] = { 3,4,1,2,2,2,3,3,5 }; getMode(arr, 0, sizeof(arr) / sizeof(arr[0]) - 1); cout << "众数为：" << mode << " 重数为：" << n << endl; }程序运行结果如下：
