169 Majority Element

<p>Given an array of size <i>n</i>, find the majority element. The majority element is the element that appears <b>more than</b> <code>⌊ n/2 ⌋</code> times.</p>

这道题本人也不会做，于是先查了一波代码：

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

看到代码后，不禁对这段代码之作者产生了深深的敬仰之情~

其实这段代码的本意是将两个互不相同的数相互抵消，这样子留下来的那个数就肯定是数量大于一半的那个数啦~

思路简单易懂，复杂度也控制在<code>O(n)</code>,这段代码真是美啊