一、题述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于  [n/2]  的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

二、题解

1、方法一：排序法

由题意知，我们需要提取出出现次数大于总数一半的“众数”，由数学原理易得，排序后[n/2]处的数必为我们所需要的那个数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

复杂度分析

时间复杂度：数组排序的时间复杂度为O(nlogn)

空间复杂度：O(logn)

2、方法二：哈希表

我们可以采用类似于Python中键值对的方法，对数组进行遍历，收集所有的元素以及他们出现的次数。我们也可以用类似于擂台的办法，保留出现次数最多的数字，以此避免对整个数组的遍历。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) { 
/**
迭代器遍历
，类似于如下代码：
for(int i=0;i<arr.length;i++){
int num = arr[i];
...
}
**/
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

复杂度分析

• 时间复杂度：O(n)， n 是数组 nums 的长度.

• 空间复杂度：O(n).

3、方法三：Boyer-Moore 投票算法（Leetcode解法）

有一说一，没太看明白emmm