Majority Element

https://leetcode.com/problems/majority-element/description/

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.

Thoughts

因为最多元素比总数一半还多，也就是把这个元素看成+1, 其它看成-1, 总和会是正的。利用此思想每遇到和target相同的+1, 否则-1，当为负时就把当前换成target。任何一个不是解的target都会被冲为负，遇到解后会一直保持正数直到结束。

Code

/*
 * @lc app=leetcode id=169 lang=cpp
 *
 * [169] Majority Element
 */
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        const int N = nums.size();
        if (N == 1) return nums[0];
        if (N == 0) return 0;
        int count = 1, target = nums[0];
        for (int i = 1; i < N; ++i) {
            if (target != nums[i]) --count;
            else ++count;
            if (count < 0) {
                target = nums[i];
                count = 0;
            }  
        } 
        return target;
    }
};

Analysis

时间O(N), 空间O(1)