Krains's Blog

vuePress-theme-reco Krains    2020 - 2021
Krains's Blog Krains's Blog

Choose mode

  • dark
  • auto
  • light
Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)
author-avatar

Krains

80

Article

22

Tag

Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)

229. 求众数 II

vuePress-theme-reco Krains    2020 - 2021

229. 求众数 II


Krains 2020-08-04 16:03:03 数学

# 题目链接 (opens new window)

# 解题思路

明确一点就是众数最多只能有2个,如果两个数出现的次数分别为a和b,a>n/ 3,b>n/3,这两个数为众数,设其他数字的出现次数为c,那么a+b+c=n,有a+b>2n/3,c<n/3,因此最多只能有两个众数。

我们每次移除3个不同的数,因为a和b都大于c,a-c以及b-c都大于0,最后剩下的就一定是众数。

但是众数有可能是0个或者1个,因此为了确认选出来的两个数是否是众数,还要进行一次遍历确认其出现次数是否大于n/3

# 代码编写

  • 如果当前元素等于cand1,则cand1次数加1
  • 如果当前元素等于cand2,则cand2次数加1
  • 如果都不等,如果其中候选者的次数为0,则更换候选
  • 若num符合前面3个条件的其中一个,就要需要考虑下一个元素,因为如果满足了前面3个条件的其中一个num就成了候选者,如果前面3个条件都不满足,说明cand1、cand2与当前元素num各不相等,且cand1和cand2至少存在1个,那么同时移除一个cand1、cand2和num
  • 最后为了确保选出来的候选者是众数,还要一次遍历统计判断是否为众数
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0, cnt1 = 0;
        int cand2 = 0, cnt2 = 0;
        for(int num : nums){
            if(num == cand1){
                cnt1++;
                continue;
            }

            if(num == cand2){
                cnt2++;
                continue;
            }

            // 更换候选1
            if(cnt1 == 0){
                cand1 = num;
                cnt1 = 1;
                continue;
            }

            // 更换候选2
            if(cnt2 == 0){
                cand2 = num;
                cnt2 = 1;
                continue;
            }
			
            // 同时移除一个cand1、cand2和num
            cnt1--;
            cnt2--;
        }

        // 还需一次遍历判断候选是否为众数
        cnt1 = cnt2 = 0;
        List<Integer> list = new ArrayList<>();
        for(int num : nums){
            if(num == cand1){
                cnt1++;
            }else if(num == cand2){
                cnt2++;
            }
        }
        if(cnt1 > nums.length / 3)
            list.add(cand1);
        if(cnt2 > nums.length / 3)
            list.add(cand2);
        
        return list;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# 复杂度分析

  • 时间复杂度:O(N)O(N)O(N),一次遍历
  • 空间复杂度:O(1)O(1)O(1)
  • 题目链接
  • 复杂度分析