众数问题-分治

program-ai-cv-ml-se-fighting 2021-08-04 原文

题目：

找出给定递增序列的众数，并求出众数在序列中出现的次数（重数）

思路：

一开始看到题目写的时候，用的是O(n)级别的一遍扫描法，边扫描边统计，现在用分治法来写一下

对于一个数组，首先我假设中间元素是众数，并且用区间内扫描法来定位所有与中间数相等的数，区间标记为[p,r]，个数记为midcnt

这样就通过p,r将区间分成了三段，接下来要做的应该是向[left,p-1]和[r+1,right]分别拓展，看这两个区间内是否会出现众数

在拓展的时候我们可以做一个优化，如果某个区间所有的元素个数比中与间元素（目前假设的众数）相等的数的个数还少，那么这个区间内不可能出现众数，可以不用再去找，如果找到的新的数比目前的重数大，则新的众数诞生。

上代码：

 1 #include<iostream>
 2 using namespace std;
 3 int a[] = { 1,1,2,2,2,3,3,3,3,3,4,4,5,6,7,7,7 };
 4 int len = sizeof(a) / sizeof(a[0]);
 5 int num;
 6 int cnt=0;
 7 void pos(int left, int right,int mid, int &p, int &r) {
 8     int i;
 9     for (i = left; i <= right; i++) {
10         if (a[i] == a[mid]) {
11             break;
12         }
13     }
14     p = i;//mid的左边界
15     for (i = p + 1; i <= right; i++) {
16         if (a[i] != a[mid]) {
17             break;
18         }
19     }
20     r = i - 1;//mid的右边界
21 }
22 void getMaxCnt(int left, int right) {
23     int mid = (left + right) / 2;
24     int p;
25     int r;
26     pos(left, right, mid, p, r);
27     int midcnt = r - p + 1;
28     if (midcnt > cnt) {
29         num = a[mid];
30         cnt = midcnt;
31     }
32     if (p - left > cnt) {
33         getMaxCnt(left, p - 1);
34     }
35     if (right - r - 1 > cnt) {
36         getMaxCnt(r + 1, right);
37     }
38 }
39 int main() {
40     getMaxCnt(0, len - 1);
41     cout << num << endl;
42     cout << cnt << endl;
43 
44     return 0;
45 }