169. 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.
Solution
题意即寻找在给定数组中出现次数超过半数的数字，题目保证这样的数字存在。我的解法是先排序，那么中间那个数必定是我们要的数，因为我们要的数对的个数是超过半数的，无论它从哪里开始，总能够覆盖中间的下标，代码如下
class Solution {
public:
int majorityElement(
vector<int>& nums) {
sort(nums.begin(),nums.end());
return nums[nums.size() /
2];
}
};
在翻看题解的过程中，发现了一种很高效的算法——Boyer-Moore Majority Vote Algorithm，能够在O(N)的时间和O(1)的空间内找到超过半数的数字，实现很简单，但是我还是没能理解这样做的道理，如果有好的理解方式，请不吝指教。摩尔投票算法的描述就是：算法在局部变量中定义一个序列元素(m)和一个计数器(i)，初始化的情况下计数器为0. 算法依次扫描序列中的元素，当处理元素x的时候，如果计数器为0，那么将x赋值给m，然后将计数器(i)设置为1，如果计数器不为0，那么将序列元素m和x比较，如果相等，那么计数器加1，如果不等，那么计数器减1。处理之后，最后存储的序列元素(m)，就是这个序列中最多的元素。代码如下
class Solution {
public:
int majorityElement(
vector<int>& nums)
{
int cand;
int count =
0;
for(
int i =
0; i<nums.size();i++)
{
if(i ==
0 ||count ==
0)
{
cand = nums[i];
count =
1;
}
else if(nums[i] == cand)
count++;
else
count--;
}
return cand;
}
};
