A - 必做题 - 1

给出n个数，zjm想找出出现至少(n+1)/2次的数，现在需要你帮忙找出这个数是多少？

Input

本题包含多组数据：每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。

Output

对于每一组数据，你需要输出你找到的唯一的数。

Sample Input

51 3 2 3 3111 1 1 1 1 5 5 5 5 5 571 1 1 1 1 1 1

Sample Output

解题思路

本题要找到出现了(n+1)/2次及以上的数，那么这个数一定是唯一的，所以可以先升序排序。然后计算相同的数的个数，如果那个数的个数超过了(n+1)/2，那么遍历结束，输出那个数。

Codes

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn = 1e6 + 10;int n,a[maxn],num;int main(){
       while (scanf("%d",&n) != EOF){
           int tag = 0;        memset(a, 0, sizeof(a));        for (int i = 1; i <= n;i++)            cin >> a[i];        num = (n + 1) / 2;        sort(a+1, a + n+1, less
       
        ());        for (int i = 1; i <= n;i++){
               if(a[i]!=a[i+1]){
                   tag = i-tag;                if(tag>=num){
                       cout << a[i] << endl;                    break;                }            }        }    }    return 0;}