求解众数问题

给定一个整数序列，每个元素出现的次数称为重数，重数最大的元素称为众数。编写一个实验程序对递增有序序列a求众数

分治法实现

本题的分治策略比较明确,不过使用分治策略解决众数问题需要原集合有序，在原集合无序的情况下需要对其排序，我建议在这里使用sort()先对数组进行排序(虽然题目里已经给出输入是递增的)

分治的主要思路如下

  1. 首先假设中间的元素 a[mid] 是众数

  2. 由两边向中间遍历，找到一个子序列,其值全部都等于 a[mid] ,记录下该段的 l 与 r 边界,统计重数和众数

  3. 这样就将一个数组分为三部分(左侧区域,中间的相等子序列,右侧区域)，我们再对左右部分执行上述步骤,即可分治求解

只有集合有序的时候才能保证从两侧向中间遍历的时候,找到的第一个数就可以标定连续的一串相等的数的边界

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
#include <bits/stdc++.h>
using namespace std;
int num, mid, l, r, maxcnt = 0;
vector<int> a;
void split(int low, int high)
{
    mid = (low + high) / 2;
    for (l = low; l <= high; l++)
        if (a[l] == a[mid])
            break;
    for (r = high; r >= low; r--)
        if (a[r] == a[mid])
            break;
}
void Getmaxcnt(int low, int high)
{
    if (low > high)
        return;
    split(low, high);
    maxcnt <= r - l + 1 ? num = a[mid], maxcnt = r - l + 1 : false;
    Getmaxcnt(low, l - 1);
    Getmaxcnt(r + 1, high);
}
int main()
{
    int tmp;
    while (cin >> tmp)
        a.push_back(tmp);
    sort(a.begin(), a.end());
    for (auto i : a)
        cout << i << " ";
    Getmaxcnt(0, a.size() - 1);
    cout << "\nModeValue:\t" << num << "\nCount:\t" << maxcnt << endl;
    return 0;
}

哈希表实现

众所周知哈希表是个 K:V 结构的数据结构，其中 K 是键，V 是值,在查找众数的过程中,将元素作为键,出现次数作为值,最后遍历整个哈希表,即可找到最大值

求解本题可以直接使用 C++ 提供的 unordered_map 容器,该容器底层使用了哈希表,支持直接将键作为下标进行操作

示例代码大量使用三目运算符和 lambda 表达式,请酌情理解

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> m;
int main()
{
    int n;
    while (cin >> n)
        m.find(n) == m.end() ? m[n] = 1 : m[n]++;
    auto it = max_element(m.begin(), m.end(), [](auto a, auto b) -> bool
                          { return a.second < b.second; });
    cout << "ModeValue:\t" << it->first << "\nCount:\t" << it->second << endl;
    return 0;
}