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.

思路分析

这道题目有一个限制条件是majority element元素总是存在的，这样的话在编写代码的时候就相对简单了，思路也比较巧妙，代码如下：

int majorityElement(int* nums, int numsSize) 
{
    int cnt = 0;
    int result = 0;
    for(int i = 0; i < numsSize;++i)
    {
        if(0 == cnt) 
        {
            result = nums[i];
        }
        
        if (result == nums[i])
        {
            ++cnt;
        }
        else
        {
            --cnt;
        }
    }
    int num = 0;
    /*check if result is the majority*/
    for(int i = 0;i < numsSize;i++)
    {
        if(result == nums[i])
        {
            num++;
        }
    }
    
    if(num > (numsSize/2))
        return result;
    else
    {
        printf("There is no majority Element.num = %d \n",num);
        return INT_MAX;
    }
    
}

2020.10.29更新
看极客时间里的视频再次刷到这个题，在5 6种方法中hashmap这种解法更易理解和手写AC，完整代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map <int,int> counter;
        int n = nums.size();
        for(int i = 0;i < nums.size();i++)
        {   
            if(++counter[nums[i]] > n / 2)
                return nums[i];
        }

        return 0;
    } 
};

2021.05.24更新
题目中要求时间复杂度为O(n)，空间复杂度为O(1)，因此上面hashmap方案存在问题。
使用C++实现文章开头代码：(题目中限定存在多数元素，因此无需检测）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int result = 0,cnt = 0;
        for(int i = 0;i < nums.size();i++)
        {
            if(cnt == 0)
                result = nums[i];

            if(nums[i] == result)
                cnt++;
            else
                cnt--;
        }

        return result;
    }
};