HDU1029 - Ignatius and the Princess IV【水题】

给你n个数字，请你找出出现至少(n+1)/2次的数字。

输入

本题包含多组数据，请处理到EOF：

每组数据包含两行。

第一行一个数字N(1<=N<=999999) ，保证N为奇数。

第二行为N个用空格隔开的整数。

输出

对于每组数据，输出一行，表示要求找到的那个数

样例输入

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

样例输出

思路：第一种思路是将数组排序，由于其出现（n+1）/2 次，故中位数一定是要找的那个数。时间复杂度O（nlogn）

#include<cstdio>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

const int maxn=1000005;

int a[maxn],b[maxn];

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        memset(a,0,sizeof(a));

        //int t;

        for(int i=0;i<n;++i)

        {

            scanf("%d",&a[i]);

        }

        sort(a,a+n);

        printf("%d\n",a[(n-1)/2]);

    }

    return 0;

}

另一种就是网上题解中比较常见的了，不得不说思路确实很棒，复杂度O(n)

#include<iostream>

#include<cstring>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<stack>

#include<queue>

using namespace std;

const int N = 1000005;

int a[N];

int main()

{

    int n;

    while(~scanf("%d", &n))

    {

        int num = 0;

        int ans = -1;

        for(int i=0; i<n; i++)

        {

            scanf("%d", &a[i]);

            if(num == 0)

            {

                ++num;

                ans = a[i];

            }

            else

            {

                if(ans != a[i])

                    num--;

                else

                    num++;

            }

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

HDU1029 - Ignatius and the Princess IV【水题】

最新文章

热门文章