TRZ_2007 的博客

TRZ_2007 的博客

题解 AT1512 【採点/Grading】

posted on 2019-09-07 16:30:07 | under 题解 |

这题其实就是著名的主元素问题:让你求集合 $A$ 中有那个数出现次数超过一半。

Sol 1:枚举法:

方法:两两比较,复杂度是 $$Θ(n^2)$$

TLE预定……

Sol 2:排序法:

方法:若假设有这样的一个数,那么TA一定出现数据排序后在 $n/2$ 的这个位置。只需要进行计数即可。复杂度为:

$$Θ(nlgn)$$

code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int n,m,ans;
int a[N];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(a[i] == a[(n+1)/2]) ans++;
    if(ans > n/2) printf("%d\n",a[(n+1)/2]);
    else printf("?\n");
}

其实,还可以用 $O(n)$ 的方法来解决,只不过楼上大佬已经说了,就不讲了