学步园

小记：细节决定成败。 最近又被朋友问及到这样一道题，说如果大数据，如何O(n)实现。实在没想通

思路：题目没说给定的数可能有多大，如果是long long型，就不能用数组来叠加了。这里选择用map将long long 映射到int，进行计数。

因为对于n=2这个是一个特殊情况。我们必须输出这两个数，它们都是special number。

代码：

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

map<long long, int>mp;
map<long long, int>::iterator q;

int main(){
    long long n,m, ans, T;
    bool flag;
    while(cin>>n){
        mp.clear();
        flag = 0;T = n;
        while(n--){
            cin>>m;
            mp[m]++;
            if(mp[m] == (T+1)/2){
               if(flag)cout<<" ";flag=1;cout<<m;}
        }
        cout<<endl;
    }

    return 0;
}

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

const int MAX_ = 130;

int p[MAX_];

map<long long, int>mp;
map<long long, int>::iterator q;

int main(){
    //freopen("f:\\out.txt","w",stdout);
    long long n,m, ans, T;

    while(cin>>n){
        mp.clear();
        ans = 0;T = n;
        while(n--){
            cin>>m;
            mp[m]++;
            if(mp[m] == (T+1)/2){
                p[ans++] = m;
            }
        }

        cout<<p[0];
        for(int i = 1; i < ans; ++i)
            cout<<" "<<p[i];
        cout<<endl;
    }

    return 0;
}

我们从头一个数一个数的判断，如果某一个数是最多的那个数，那么去掉这个数后剩下的数中，这个数还会是最多的，

我们利用抵消原理，如果碰上两个不相同的数，那么我们就要抵消掉一个，

假设从第一个开始，用cnt来计数，res表示计数的数，当当前的数等于res时，cnt++

不等于时，cnt--，

而若cnt=0的时候，那么说明res这个数肯定就不是最多的那个数，此时我们再将res和cnt初始化为当前的数，即res等于当前的数，cnt=1

这个想法简直是太棒了！

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 1000010;
const int N = 100010;
const int INF = 0x7fffffff;



int main(){
	int n, cnt, k, res;
	while(~scanf("%d",&n)){
        cnt = 0;
        while(n--){
            scanf("%d",&k);

            if(cnt == 0)res = k,cnt = 1;
            else {
                if(k == res)cnt++;
                else cnt --;
            }
        }
        printf("%d\n",res);
	}
	return 0;
}