Blackops

初心易得，始终难守

0%

NYOJ 95 众数问题（分治法求众数）

发表于 分类于 ，

众数问题
时间限制：3000 ms | 内存限制：65535 KB
难度：3

描述
所谓众数，就是对于给定的含有N个元素的多重集合，每个元素在S中出现次数最多的成为该元素的重数，

多重集合S重的重数最大的元素成为众数。例如：S={1,2,2,2,3,5}，则多重集S的众数是2，其重数为3。

现在你的任务是：对于给定的由m个自然数组成的多重集S，计算出S的众数及其重数。

输入
第一行为n，表示测试数据组数。(n<30)
每组测试的第一行是一个整数m，表示多重集S中元素的个数为m
接下来的一行中给出m(m<100)个不大于10万的自然数
（不会出现不同元素出现的次数相同的情况，如：S={11,11,22,22,33,33}）。
输出
每组测试数据输出一行，包含两个数，第一个是众数，第二个是其重数，中间以空格隔开。
样例输入
1
6
1 2 2 2 3 5
样例输出
2 3

题目链接：NYOJ 95
由于算法课讲了用分治的思想求众数，而我以前不知道有这种方法（虽然时间复杂度上都是$nlog(n)$的，但是空间复杂度分治似乎比map更优一点，sort后再遍历的这种方法太简单就不讲了），想着还是要好好学习一波，打好基础。
本来前几周就该写了，但是由于眼瞎导致一直$WA$到怀疑人生，刚才发现原来$n$是数据组数，$m$才是数组长度（温柔是你的美……）
然后中间又去膜了下快排的基本原理，发现在快排中统计$pivot$的个数的话需要考虑一些边界问题，还不如重新$O(N)$地再扫一次好了。
主要过程如下：

  1. 假设当前枢轴元素为$pivot$，将$pivot$归位后的位置为$mid$（偷懒用nth_element()也行），然后统计出$pivot$的个数，先拿去更新全局最优解。
  2. 假设有出现次数比全局最优解更多的数，记为$mode_t$。
    1. $mode_t=pivot$，本次递归本身已经计算过，无需再考虑。
    2. $mode_t \lt pivot$，只可能在左半边，递归处理$[l,mid-1]$
    3. $mode_t \gt pivot$，只可能在右半边，递归处理$[mid+1,r]$

这样一来时间复杂度是$O(Nlog(N))$，空间复杂度基本上是$O(N)$。这玩意儿写完发现跟$KD-tree$递归查询的剪枝很像啊，就是用全局最优解来剪枝
代码：

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 110;//数组长度最大为100，而不是30……
int arr[N], cnt, mode;

void solve(int l, int r)
{
    int temp = arr[l];
    int i = l, j = r;
    while (i < j)
    {
        while (i < j && arr[j] >= temp)
            --j;
        while (i < j && arr[i] <= temp)
            ++i;
        swap(arr[i], arr[j]);
    }
    swap(arr[l], arr[i]);
    int tcnt = 0;
    for (int k = l; k <= r; ++k)
        if (arr[k] == arr[i])
            ++tcnt;
    if (tcnt > cnt)
    {
        cnt = tcnt;
        mode = arr[i];
    }
    if (i - 1 - l + 1 > tcnt)
        solve(l, i - 1);
    if (r - (i + 1) + 1 > tcnt)
        solve(i + 1, r);
}
int main(void)
{
    int n, i, T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (i = 1; i <= n; ++i)
            scanf("%d", arr + i);
        cnt = 0;
        solve(1, n);
        printf("%d %d\n", mode, cnt);
    }
    return 0;
}