1186：出现次数超过一半的数

1186：出现次数超过一半的数
【题目描述】
给出一个含有n（0 < n <= 1000）个整数的数组，请找出其中出现次数超过一半的数。数组中的数大于-50且小于50。

【输入】
第一行包含一个整数n，表示数组大小；

第二行包含n个整数，分别是数组中的每个元素，相邻两个元素之间用单个空格隔开。

【输出】
如果存在这样的数，输出这个数；否则输出no。

【输入样例】
3
1 2 2
【输出样例】
2

#include
using namespace std;
int main()
{
    int n,a[1550]={0},x;
    double s=0.0;
    cin>>n;
    s=n/2.0;
    for(int i=0;i>x;
        a[x]++;
    }
    for(int i=0;i<1515;i++)
    {
        if(a[i]>s)
        {
            cout<return 0;
        }
    }
    cout<<"no";
    return 0;
}

未通过 60分
测试点1: 答案错误 600KB 2MS
测试点2: 答案正确 604KB 2MS
测试点3: 答案正确 600KB 2MS
测试点4: 答案正确 604KB 2MS
测试点5: 答案错误 600KB 1MS
测试点6: 答案正确 608KB 2MS
测试点7: 答案正确 596KB 2MS
测试点8: 答案错误 604KB 2MS
测试点9: 答案正确 604KB 1MS
测试点10: 答案错误 600KB 2MS

出错的主要原因应该是没有把负数的情况考虑进去，可以用一个二维数组存储输入的数及其出现的次数，然后循环存储比较即可。代码修改如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[1550][2]={0},x;
    double s=0.0;
    cin>>n;
    s=n/2.0;
    int index=0;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        int find=0; 
        if(index>0){
            for(int j=0;j<index;j++){
                if(a[j][0]==x){
                    find=1;
                    a[j][1]++;
                }
            } 
            if(find==0){
                
                a[index][0]=x;
                a[index][1]=1; 
                index++;
            }
        } else{
            a[0][0] = x;
            a[0][1] = 1;
            index++;
        } 
    }
    
//    for(int i=0;i<index;i++){
//        printf("a[%d][0]=%d,a[%d][1]=%d\n",i,a[i][0],i,a[i][1]);
//    }
    
    for(int i=0;i<1515;i++)
    {
        if(a[i][1]>s)
        {
            cout<<a[i][0]<<endl;
            return 0;
        }
    }
    cout<<"no";
    return 0;
}
 

既然数大于-50，且小于50，那么实际的数只有99个，所以定义一个100个元素的数组即可，然后统计其出现的次数。

#include <iostream>
using namespace std;
int main()
{
    int a[100] = {0};
    int n,d,i;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin >> d;
        a[d+50]++;
    }
    for(i=0;i<n;i++)
        if(d[i] > n/2)
        {
           cout<<d[i] - 50;
            break;
        }
    if(i==n)
        cout<<"no";
    return 0;
}