【題解】HDU 1029 Ignatius and the Princess IV

【題目敘述】https://vjudge.net/problem/HDU-1029

【方法1】直接統計數字的出現次數

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N){
        int x;
        map <int, int> mp;
        for (int i=0; i<N; i++){
            cin >> x;
            mp[x]++;
        }
        int mx = 0;
        int ans = 0;
        for (auto i: mp){
            if (i.second > mx){
                mx = i.second;
                ans = i.first;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

【方法2】排序求中位數,O(N log(N))

  • 題目保證數字個數 N 為奇數。
  • 且特殊數字出現的次數至少 (N+1)/2 次。
  • 數列排序後的中位數即為答案。
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N){
        int a[N];
        for (int i=0; i<N; i++){
            cin >> a[i];
        }
        sort(a, a+N);
        cout << a[N/2] << '\n';
    }
    return 0;
}

【方法3】用眾數出現的次數抵銷其它數字出現的次數,O(N)

  • 題目保證數字個數 N 為奇數。
  • 且特殊數字出現的次數至少 (N+1)/2 次。
  • 這個特殊數字出現的次數,一定足以抵銷其它數字出現次數的總和。
  • 隨便抓一個數字當答案(ans),cnt = 1,當下一數字與ans相同,cnt++,否則cnt–,當cnt=0時,重置ans為當下遇到的數字。最後留下的ans即為答案。
#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    while (cin >> N){
        int a[N];
        for (int i=0; i<N; i++){
            cin >> a[i];
        }
        int ans;
        int cnt = 0;
        for (int i=0; i<N; i++){
            if (cnt == 0){
                ans = a[i];
                cnt = 1;
            }else{
                if (a[i] == ans) cnt++;
                else cnt--;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
分享本文 Share with friends