LeetCode 169. Majority Element My Submissions Question

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

思路

多数投票嘛，这个题目当年NB哄哄的数据库老师在课堂上提到过，至今印象深刻，跟我们说选班长的时候画正字就是在浪费空间（当然要保证半数通过的前提）。
假设当前候选人A唱了三票，那么小黑板上A的“正”字记了三笔；这时候有了B的一票，由于我们只要统计排名第一的人，此时可以把A的正字划去一票，而不是重新记一个“B，一票”。因为照这样计算，如果B再唱了两票，那两个人的票刚好抵消，小黑板被擦干净，这时候不管是谁得了一票就写在小黑板上重新计数啦

思路2

设想一下排序后的数列，如果有个元素占了超过半数的位置，那么它肯定也是这个数列的中位数。参考快速排序的思想，可以在O(n)的复杂度找到这个中位数，它也就是要得到的结果。（参考数组第k大数的那个递归方法）

代码（思路1）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majNum = -1;
        int majCount = 0;
        int numSz = nums.size();
        for(int i=0; i<numSz; i++){
            if(majNum != nums[i]){
                if(majCount == 0){
                    majNum = nums[i];
                    majCount = 1;
                } else {
                    majCount--;
                }
            } else {
                majCount++;
            }
        }
        return majNum;
    }
};