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

題目連結：[kuangbin帶你飛]專題十二 基礎DP1 B - Ignatius and the Princess IV

題意

給n(奇數)個數，定義特殊的數為在序列中出現次數不少于(n+1)/2次的數，找出這個特殊的數

思路

1. 我ac的思路是直接排序，然後一次循環進行對出現次數最大值的判斷。
2. 還有一種方法是排序後找第n/2大的數，因為特殊數出現次數超過一半，是以排序後中位數一定是特殊數。

3. 看了大牛部落格才發現還有更妙的一種方法，上面兩種方法都基本是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 = ;
int a[N];

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

思路3

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

const int N = ;
int a[N];

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