SOJ--4389: 川大贴吧水王

墨蓝 2022-08-06 04:21 269阅读 0赞

## 描述      \_L的室友HZ喜欢在川大贴吧上发帖，据传说，HZ在川大贴吧上发的贴子数已经超过了该贴吧贴子总数的一半，被江湖人封为川大贴吧水王，你能帮\_L迅速找出这位川大贴吧水王HZ的ID吗？   已知川大贴吧贴子总数为n，给出n个贴子作者的ID，求HZ的ID。   Input      输入文件包含多组测试数据。第一行为测试的数据组数T(T<=40)。   接下有T组数据，第一行输入贴子总数n(1<=n<=10000000),接下来的一行有n个正整数，分别为每位贴子作者的ID号(该ID号为不超过10^9的正整数)   Output      输出T行，每行为该组测试数据的川大贴吧水王HZ的ID。   Example Input      2   3   1 2 2   5   1 2 3 3 3   Example Output      2   3   Author      \_L    ##

解析：常规来看，可以对输入的id号进行排序，然后进行查找，但是看到总数n最大为10000000，猜想应该会超时，但是还是快速敲了代码测试了下，结果果然超时，所以这个暴力方法是行不通的

贴一下自己超时代码

#include<iostream>
    #include<algorithm>
    using namespace std;
    //定义存放数据的数组，设值为全局变量
    const int M=10000000+5;
    int a[M];
    int main()
    {
    	int T;
    	//输入T组数据
    	cin >> T;
    	while(T--)
    	{
    		int n;
    		cin >> n;
    		//输入数据
    		for(int i=0; i<n; ++i)
    		{
    			cin >> a[i];
    		}
    		//对输入的数组进行排序
    		sort(a,a+n);
    		//找出现次数大于n/2的id号
    		int cnt=1, value=a[0];
    		for(int i=1; i<n; ++i)
    		{
    			if(a[i]==value)
    			{
    				cnt++;
    				//判断cnt是否符合条件
    				if(cnt>n/2)
    				{
    					cout << value << endl;
    					break;
    				}
    			}else{
    				value=a[i];
    				cnt=1;
    			}
    		}
    	}
    	return 0;
    }

然后再仔细看题进行分析，题目中有个重要的信息就是所找的id号出现的次数大于总次数的一半，可以利用这个原理进行优化代码。

一次遍历数组就可以得到，利用两个变量 k 和 j 来保存中间的值，其中k保存每次比较的值，j 存放次数，遍历数组，如果当前数组a\[i\]等于k则j++反而j--，也就是利用抵消的思想，因为最终要找的数出现的次数大于总数的一半，所以这个数的次数j最后一定是大于0的，也就是利用这个原理可以使复杂度降到O(n)

贴下AC代码(注意不要用cin、cout)

#include<stdio.h>
    const int M=10000000+5;
    int a[M];
    int search(int A[], int length)
    {
    	int k, j=0;
    	for(int i=0; i<length; ++i)
    	{
    		if(j==0)
    		{
    			k=A[i];
    		}
    		if(k==A[i])
    		{
    			++j;
    		}else{
    			--j;
    		}
    	}
    	return k;
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		int n;
    		scanf("%d",&n);
    		for(int i=0; i<n; ++i)
    		{
    			scanf("%d",&a[i]);
    		}
    		//找出出现次数大于一半的ID号
    		printf("%d\n",search(a,n));
    	}
    }