Ignatius and the Princess IV
先搬中文
Descriptions: 給你n個數字，你需要找出出現至少(n+1)/2次的數字 現在需要你找出這個數字是多少？ Input本題包含多組資料，請處理到EOF： 每組資料包含兩行， 第一行一個數字N(1<=N<=999999) ，保證N為奇數， 第二行為N個用空格隔開的整數，
Output
對于每組資料，輸出一行，表示要求找到的那個數
Sample Input
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
Sample Output
3 5 1
題目鏈接：
https://vjudge.net/problem/HDU-1029
找出數列里面出現次數多于n/2的的元素
既然次數大于n/2，那么例如3、2、3、1、3、2、3
- 去掉3 2
- 去掉3 2
- 去掉3 1
- 還剩一個3
由此可得我們按照序列一次掃描，把第一個數字x賦值給ans，計數器cnt=0
若是后來數字x與ans相同，則cnt++，否則cnt-- 若cnt為0，則重新找（不用倒回開頭）以此循即可
AC代碼
#include <bits/stdc++.h> #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x, y) memset(x, y, sizeof(x)) #define Maxn 1000 using namespace std; int main() { int n,x,ans,cnt; while(cin>>n) { cnt=0; for(int i=0; i<n; i++)//存數 { cin>>x; if(cnt==0)//計數器為0，重新計數 { ans=x; cnt=1; } else { if(ans==x)//相同，計數器+1 cnt++; else//不同-1 cnt--; } } cout<<ans<<endl; } return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/206281.html
標籤：其他