169. 多数元素（简单）

在这里插入图片描述

方法一：sort排序，时间复杂度为O(nlogn)

思路

我自己的写法用了最简单的方法，首先使用 sort() 对数组元素按照从小到大进行排序，然后依次遍历每个元素，如果该元素的出现次数大于 n/2 ，那么就返回该元素。

代码

class Solution {
public:int majorityElement(vector<int>& nums) {int n = nums.size();int cnt = nums.size() / 2;// 对元素按照从小到大进行排序sort(nums.begin(), nums.end());// 元素的出现次数int show = 1; for(int i=1; i<n; ++i){// 如果和前一个元素一样，出现次数加一if(nums[i] == nums[i-1]){show += 1; // 判断是否已经达到要求if(show > cnt)  return nums[i];}// 如果和前一个元素不同，重新计数else show = 1;}return nums[n-1];}
};

我还是想复杂了，由于该元素出现次数大于 50% ，所以直接返回 nums 的中间元素即可。

代码

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

方法二：优化「 Boyer-Moore 投票算法」

思路

题目的优化要求是 时间复杂度为O(n)，空间复杂度为O(1) ，而我方法一使用了 sort() ，时间复杂度为O(nlogn)，空间复杂度为O(n)，显然无法满足要求。
Boyer-Moore 投票算法的思想类似于同归于尽消杀法 ：

由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。

如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count++；

如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。此时前方阵营兵力count --。（即使双方都死光，这块高地的旗帜 winner 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）

当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。

就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营，winner 就是多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

代码

class Solution {
public:int majorityElement(vector<int>& nums) {int winner = nums[0];int count = 1;for(int i=1; i<nums.size(); ++i){// 阵营没有人，新来的人默认成为新的winnerif(count == 0){winner = nums[i];count ++;}// 新来的人和winner同一阵营else if(nums[i] == winner){count ++;}// 新来的人和winner不同阵营 那么需要抵消一个else{count --;}}return winner;}
};