Ignatius and the Princess IV

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32767K (Java/Other)

Total Submission(s) : 7   Accepted Submission(s) : 3

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

Sample Output

3
5
1

Author

解题思路：

给出n个数。n为奇数。求在里面至少出现(n+1)/2 次的那个数。

方法一：

同等消除。比方数 -1 -2  3 3 3 -2 ，消除一次-1 3 -2 去掉。剩余3 3 -2 。再消除一次 剩余3,3就是所求。

代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int num,cnt,r;
    while(scanf("%d",&n)!=EOF)//一定得写上。EOF 
    {
        cnt=0;
        while(n--)
        {
            scanf("%d",&num);
            if(cnt==0)
            {
                r=num;
                cnt=1;
            }
            if(num==r)
                cnt++;
            else
                cnt--;

        }
        printf("%d\n",r);
    }
    return 0;
}

方法二：hash打表。

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=1000005;
int hash[maxn];

int main()
{
    int n,num,r;
    while(scanf("%d",&n)!=EOF)
    {
        memset(hash,0,sizeof(hash));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&num);
            hash[num]++;
            if(hash[num]>n/2)
            {
                r=num;//找到了也不能break掉。由于有可能还没有输入完成
            }
        }
        printf("%d\n",r);
    }
    return 0;
}