学步园

一、 题目

给出一个大小为n的数组，找出主元素，主元素是出现次数大于n/2的数。

假设数组不为空，主元素一定存在。

二、 分析

这道题在面试中很容易见到，找出出现次数大于全体个数一半的数。思路是只需要设置一个计数器，只有它为0时才改变主元素的值，如果出现等于主元素的数则加1，否则减1。即如果有该数那么一定会找出主元素。

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int len = num.size();
        int count = 0;
        int major;
        for(int i = 0; i < len; i++){
            if(count == 0)
                major = num[i];
            if(major == num[i])
                count++;
            else
                count--;
        }
        count = 0;
        for(int j = 0; j < len; j++){
            if(num[j] == major)
                count++;
        }
        if(count > len / 2 )
            return major;
    }
};

其实这道题再扩展的话就是求出出现次数前k的所有元素。

提示：最优解是，Hash + 小根堆。这个以后我们再讨论....