小朋友学经典算法（17）：分治法求众数

今天药忘吃喽~ 2022-03-01 21:00 199阅读 0赞

一组数据中，出现次数最多的数就叫这组数据的众数。  
如果有两个或两个以上个数出现次数都是最多的，那么这几个数都是这组数据的众数。  
如果所有数据出现的次数都一样，那么这组数据没有众数。

例1：1，2，3，3，4的众数是3。  
例2：1，2，2，3，3，4的众数是2和3。  
例3：1，2，3，4，5没有众数。

### 解法一： ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int cnt[100000000];
    int main()
    {
        int n;
        cin >> n;
        int a[n];
        int maxCnt = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
            cnt[a[i]]++;
            if(maxCnt < cnt[a[i]])
            {
                maxCnt = cnt[a[i]];
            }
        }
    
        sort(a, a + n);
    
        bool same = true;
        for(int i = 0; i < n - 1; i++)
        {
            if(cnt[a[i]] != cnt[a[i + 1]])
            {
                same = false;
                break;
            }
        }
    
        if(same)
        {
            cout << "没有众数" << endl;
            return 0;
        }
    
        int i = 0;
    
        while(i < n)
        {
            if(cnt[a[i]] == maxCnt)
            {
                cout << "众数：" << a[i] << ",出现的次数：" << cnt[a[i]] << endl;
            }
            i += cnt[a[i]];
        }
    
        return 0;
    }

### 解法二：分治法 ###

以a = \{1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6\}，其中间元素为a\[5\] = 3。往左边找等于3的最大位置，得到l = 4, a\[l\] = a\[4\] = 3；往右边找不等于3（即大于3）的最小位置，得到r = 6, a\[r\] = a\[6\] = 5。则可以知道，最中间的3出现的次数cnt = r - l = 2次，即maxCnt = 2次。  
接着进行分治：考虑元素3左边的a\[0\] ~ a\[l\]部分和右边的a\[6\] ~ a\[10\]部分。对这两部分各自求cnt。得到左边部分有3个2，右边部分有4个6。则最终众数是6，出现了maxCnt = 4次。  
在递归的过程中，如果左边或右边的元素数量小于maxCnt，那就不需要再递归了。这是递归的终止条件。

// 用分治法求众数
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<map>
    
    using namespace std;
    
    map<int, int> m;
    
    // 左右两边与中间数相同的数的起始、终止界限
    void split(int s[], int n, int &l, int &r)
    {
        int mid = n/2;
        // 连续两个for求与s[mid]相同的数有多少个
        for(l=0; l<n; ++l)
        {
            if (s[l] == s[mid])
                break;
        }
        for(r=l+1; r<n; ++r)
        {
            if (s[r] != s[mid])
                break;
        }
    
    }
    
    // num 众数。 maxCnt 重数
    void getMaxCnt(int &mid, int &maxCnt, int s[], int n)
    {
        int l, r;
        split(s, n, l, r);  // 进行分割。这个函数是本程序的关键
        int num = n/2;
        int cnt = r-l;
    
        // 更新出现次数最多的数
        if (cnt > maxCnt)
        {
            maxCnt = cnt;
            mid = s[num];
            m.clear();
            m[mid] = maxCnt;
        }
        else if(cnt == maxCnt)
        {
            mid = s[num];
            m[mid] = maxCnt;
        }
    
        // l表示mid左边的个数。左边的个数必须大于 maxCnt才有必要搜寻
        if (l >= maxCnt)
        {
            getMaxCnt(mid, maxCnt, s, l);
        }
    
        // n-r表示mid右边的个数, 右边数组的起始地址要变更
        if (n-r >= maxCnt)
        {
            getMaxCnt(mid, maxCnt, s+r, n-r);
        }
    }
    
    int main(void)
    {
        int s[] = {1, 2, 2, 2, 3, 3, 5, 6, 6, 6, 6};
        //int s[] = {20, 20, 30, 30};
        int n = sizeof(s)/sizeof(s[0]);
        sort(s, s + n);
    
        int maxCnt = 0;
        int num = 0;
        getMaxCnt(num, maxCnt, s, n);
    
        map<int, int>::iterator it;
        int sum = 0;
        for(it = m.begin(); it != m.end(); it++)
        {
            sum += it->second;
        }
        if(sum == n) // 唯一没有众数的情景
        {
            cout << "没有众数" << endl;
        }
        else
        {
            for(it = m.begin(); it != m.end(); it++)
            {
                cout << "众数：" << it->first << "，出现次数：" << it->second << endl;
            }
        }
    
    
        return 0;
    }

> 少儿编程、算法咨询请加微信307591841或QQ群581357582  
> ![信息学竞赛公众号.jpg][.jpg]

[.jpg]: /images/20220302/91be5e6cc8eb40a5a07d989ec0fa6d63.png