题解 | #超半的数#

//超半的数
#include<stdio.h>
int main()
{
    int n = 0;
    scanf("%d",&n);
    long long arr[1000];
    for(int i = 0;i<n;i++)
    {
        scanf("%lld ",&arr[i]);
    }
    //思路一：暴力遍历两个for循环，遇到相同则+1
//     for(int i = 0;i<n;i++)
//     {
//         int sum = 0;
//         for(int j = 0;j<n;j++)
//         {
//             if(arr[i]==arr[j])
//                 sum++;
//         }
//         if(sum>(n/2))
//         {printf("%d",arr[i]);
//          break;}
//     }
    //思路2，排序，位于中间的数字，一定是出现最多的那个
    int tmp;
    for(int i = 0;i<n-1;i++)//只需要进行n-1次排序,两两比较
    {
        int k = 1;//定义一个开关变量
        for(int j = 0;j<n-i-1;j++)//每一次排序会把最大或者最小放到最后面
        {
            if(arr[j]>arr[j+1])//把大的数字往后放(改成<即可以把小的置后)
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                k = 0;
            }
        }
        if(k==1)//说明没有进行排序,跳出
            break;
    }
    //循环之后取中间数即为所求:
    printf("%d",arr[n/2]);
    return 0;
}
//总结:排序方法明显更快