169. Majority Element

problem 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.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

algorithm thought

因为规定了majority element出现的次数肯定是数组的一半以上，所以只需要定义一个count保存出现最多次数数字的次数，遍历数组，如果重复出现则count++，否则--。如果为0，重新更换数字。因为次数肯定是一半以上，所以最后结果肯定是majority element留下来了

code

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count=0;
        int res;
        for(int num:nums){
            if(count==0){
                res=num;
                count++;
                continue;
            }
            if(num==res)
                count++;
            else
                count--;
        }
        return res;
    }
};

algorithm analysis

时间复杂度O(n)，这里最重要的是优化空间复杂度，空间复杂度到O(1)是个很大的优化