数众数

有序整数序列，数出所有众数及其个数

模块1：线性扫描

模块2：cnt计数：条件：遇见不等，计a[i-1]的cnt

 

notice: 最后一个数一定不会入栈，需要单独处理

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void findMode(vector<int> &a, stack<int> &x, stack<int> &y){
    int cnt = 1;
    y.push(-1);
    for (int i = 1; i < a.size(); i++){
        if  (a[i] == a[i-1])
            cnt++;
        else{
            if (cnt == y.top()){
                x.push(a[i-1]);
                y.push(cnt);
            }
            else if (cnt > y.top()){
                while( !x.empty() )
                    x.pop();
                while( !y.empty() )
                    y.pop();
                x.push(a[i-1]);
                y.push(cnt);
            }
            cnt = 1;
        }
    }
    if (cnt == y.top()){
        x.push(a[a.size()-1]);
        y.push(cnt);
    }
    else if (cnt > y.top()){
        while( !x.empty() )
            x.pop();
        while( !y.empty() )
            y.pop();
        x.push(a[a.size()-1]);
        y.push(cnt);
    }
}
int main(){
    vector<int> a;
    stack<int> x, y;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    findMode(a, x, y);
    while( !x.empty() || !y.empty() ){
        cout << x.top() << " " << y.top() << endl;
        x.pop();
        y.pop();
    }
    return 0;
}