【題目敘述】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;
}