题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

这道题是难度为“简单”的题目，常规的解题思路就能解，但没什么意思。比如用一个map, 记录每个数出现的次数，当次数 == n/2时，这个数即是众数。
这个解法的算法复杂度是O(n), 空间复杂度是O(n)。下面介绍一种牛逼的算法–boyer-moore算法, 是一种字符串搜索算法，我们在这里杀鸡用牛刀。
思路：假设一个数是众数，我们有一个计数器count，当遇到这个数+1, 非这个数-1, 那么count最后>0。反过来想,遇到的具体一个数（候选数）时count += 1, 下一个还是这个数时count += 1, 不是这个数时count -= 1.
当 count == 0时，遇到的数为候选数，如此循环一遍，候选数即是众数，算法复杂度O(n), 空间O(1)

代码

int majorityElement(vector<int>& nums) {
  int candidate = 0;
  int count = 0;
  for (auto n : nums) {
    if (count == 0) {
      candidate = n;
    }
    count += n == candidate ? 1 : -1;
  }
  return candidate;
}