Majority Element众数元素的解法分析

问题详见：Majority Element

      一个数组元素的众数是指非空数组中出现次数超过 ⌊n/2⌋ 的元素。题目问题描述如下：       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.

解题思路：

      这个题目有很多种解法，但是考虑到众数超过数组元素一半的这一特性，我们能使其算法复杂度降到 O(n) ，空间复杂度降到 O(1) 。利用这一特性的关键是该众数元素出现的次数比其他元素出现的次数之和还要多，所以我们可以拿其出现的次数与其他元素出现次数在搜索的时候进行比较（又一次运用神奇的数字0），具体的算法如下：

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

      上述算法中将首元素认为是中众数元素，计数为1，然后每次向后搜索就比较搜索到的元素是不是众数元素，是的话计数+1，否则计数-1，如果计数减为0说明原设定的众数元素可能不是真正的众数元素，并将众数元素设为刚搜索的数。一直循环到搜索结束，由于众数元素出现的次数比其他元素出现的次数之和还要多，所以最终的计数一定会大于0而相应的最后的众数元素一定是真正的众数元素。

上述算法提交运行结果如下：