[LintCode] Majority Number（以时间复杂度O(n)求主元素）

一个数据序列的主元素，是指序列中出现次数超过序列长度一半的元素。

法1（期望时间复杂度为O(n)）：

由于主元素出现次数超过序列长度的一半，因此，主元素一定是中位数。可以利用递归划分求中位数的方法，期望时间复杂度为O(n)。

法2：

显然，如果一个序列存在主元素，那么我们去掉序列中不同的两个数，剩下序列的主元素和原序列的主元素相同。

具体算法操作：记录两个量，当前元素x，计数cnt。初始化cnt为0；然后遍历序列，若cnt为0，则将x设为当前元素并将cnt置为1，否则，若当前元素和x相同，那么cnt++,若当前元素和x不同，那么cnt--；遍历结束以后，x即为主元素。

代码实现如下：

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number
     */
    int majorityNumber(vector<int> v) {
        // write your code here
        int x, cnt = 0;
        for(int i=0; i!=v.size(); ++i)
        {
            if(cnt==0)    x = v[i], cnt = 1;
            else    v[i]==x?++cnt:--cnt;
        }
        return x;
    }
};