HDU 1029 Ignatius and the Princess IV(水题亦有妙法)

题目链接: [kuangbin带你飞]专题十二 基础DP1 B - Ignatius and the Princess IV

** 题意 **

给n(奇数)个数,定义特殊的数为在序列中出现次数不少于(n+1)/2次的数,找出这个特殊的数

** 思路 **

  1. 我ac的思路是直接排序,然后一次循环进行对出现次数最大值的判断。
  1. 还有一种方法是排序后找第n/2大的数,因为特殊数出现次数超过一半,所以排序后中位数一定是特殊数。
  1. 看了大牛博客才发现还有更妙的一种方法,上面两种方法都基本是O(nlogn),而这个方法是O(n)
    设置一标志量num,按照原顺序依次迭代,随便假定一个解,如果a[i]==ans,num++,否则num–,当num为0时将当前a[i]作为新解。因为n为奇数
    ,且特殊值出现次数大于一半,所以任何情况下,特殊值做为解时代num不会小于1,所以最终的解一定就是特殊值。

** 代码 **

思路1

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N = 1000009;
int a[N];

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i=0; i<n; i++)
            scanf("%d", &a[i]);
        sort(a, a+n);
        int ans = a[0];
        int num = 1;
        int mmax = 0;
        for(int i=1; i<n; i++)
        {
            if(a[i] == a[i-1])
                num++;
            else
            {
                if(mmax <= num)
                {
                    mmax = num;
                    ans = a[i-1];
                }
                num = 1;
            }
        }
        if(mmax <= num)
            ans = a[n-1];
        printf("%d\n", ans);
    }
    return 0;
}

思路3

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N = 1000009;
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;
}