算法设计与分析 SCAU17088 分治法求众数（优先做）

17088 分治法求众数（优先做）

时间限制:1000MS 代码长度限制:10KB
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description

给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为
众数。例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。

求众数方法很多，现要求你用分治算法来试一试，并分析其效率。

编程任务：对于给定的由n个自然数组成的多重集S，采用分治算法编程计算S的众数及其重数。

输入格式

第1行多重集S中元素个数n；接下来的一行为集合S，有n个自然数。( n < 1000000 )

输出格式

结果输出：输出2个数，第1个数为众数，第2个为其重数。
当有多个同样重数的众数，优先输出数值更小的数的众数。

输入样例

6
1 2 2 2 3 5

输出样例

2 3

解题思路

分治

分治思想：将数据通过递归逐渐往两边进行拆分，拆分到不能再拆为止，典型例题可以来看下面这三道

23. 合并K个升序链表 配图版 归并算法(带你从最简单的求解思维过渡并理解透彻该算法）

148. 排序链表 清晰配图版 归并算法(带你从最简单的求解思维过渡并理解透彻该算法）

剑指 Offer 51. 数组中的逆序对 “分”“治” 算法教你解题

本题思路

1.我们首先假设中间的元素是众数（设中间指针是mid）
2. 然后由区间两端向中间遍历，设左指针是l，右指针是r，直到左右都出现值等于众数的数（即 a[l] == a[mid] 和 a[r] == a[mid]），记录下众数和重数
3. 这样就将一个数组分为三部分（① 区间最左端到指针l，② 指针l到指针r，③ 指针r到区间最右端），我们再对左右部分执行上述步骤

注意

1. 使用分治策略解决众数问题需要原集合有序，在原集合无序的情况下需要对其排序，建议数据输入之后先进行排序
2. 在上面第三步准备对左右部分执行递归前，可以进行剪枝，剪枝思路是：如果区间①长度小于区间②那就没必要继续递归了，因为①肯定不可能再出现重数比②大的众数了，区间③同理
3. 当有多个同样重数的众数，优先输出数值更小的数的众数，具体操作可看代码注释

更多注释可查看下方的完整代码中，有助于理解

代码如下

#include 
#include 

using namespace std;

int a[1000001];
int maxLength = 0; // 记录重数，即众数的数量
int maxNumIndex = 0; // 记录众数的下标

void fenZhi(int l, int r) {
    if(l > r)
        return;

    int ll = l, rr = r; // ll和rr分别存储此段区间的最左和最右两端
    int mid = (l + r) >> 1;

    // 从区间最左端往中间遍历，直到找到mid位置的众数区间段
    while(a[l] != a[mid] && l < mid)
        l++;

    // 从区间最右端往中间遍历，直到找到mid位置的众数区间段
    while(a[r] != a[mid] && r > mid)
        r--;

    int nowLength = r - l + 1; // 该众数区间长度
    if(nowLength >= maxLength) {
        // 当有多个同样重数的众数，优先输出数值更小的数的众数。
        if(nowLength == maxLength) {
            maxNumIndex = min(maxNumIndex, mid); // 当重数相同时，优先输出数值更小的数的众数，由于排序了，所以下标小的，数值肯定小，适用于该情况 [2,2,3,3,4]
        } else {
            maxNumIndex = mid;
        }
        maxLength = nowLength; // 更新最大长度，即重数
    }

    // 如果该众数的左边区间长度大于该众数区间的长度，才需要继续分治，否则直接剪枝就行
    if(l - ll >= nowLength)
        fenZhi(ll, l - 1);

    // 如果该众数的右边区间长度大于该众数区间的长度，才需要继续分治，否则直接剪枝就行
    if(rr - r >= nowLength)
        fenZhi(r + 1, rr);

}

int main()
{
    int i, n;
    cin >> n;

    for(i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);

    fenZhi(0, n - 1);

    cout << a[maxNumIndex] << " " << maxLength << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

最后

对我感兴趣的小伙伴可查看以下链接

• 我的掘金主页：https://juejin.cn/user/1302297507801358
• 博客主页：http://blog.zhangjiancong.top/
• 公众号：Smooth前端成长记录