【LeetCode】169. 多数元素

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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 我还是想复杂了，由于该元素出现次数大于 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];
    }
};
1
2
3
4
5
6
7
8

方法二：优化 「 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){
            // 阵营没有人，新来的人默认成为新的winner
            if(count == 0){
                winner = nums[i];
                count ++;
            }
            // 新来的人和winner同一阵营
            else if(nums[i] == winner){
                count ++;
            }
            // 新来的人和winner不同阵营 那么需要抵消一个
            else{
                count --;
            }
        }
        return winner;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

参考资料

1. 官方题解
2. 视频讲解[java]