想要精通算法和SQL的成长之路 - 摩尔投票法的运用

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 多数元素

原题链接

1.1 摩尔投票法

简单来说，假设数组 num 的众数是 x，数组长度为n。
有两个推论：

• 我们有一个票数和为sum，若记众数的票数为 +1 ，非众数的票数为 −1 ，则一定有所有数字的票数和 sum >0 。
• 如果数组的前 m 个数字的票数和为0，那么剩余的(n-m) 个数字的票数和一定 > 0，并且后面(n-m)个数字中的众数依旧是x。

那么针对本题目，求得的是多数元素，其出现次数超过数组元素个数的一半。思路如下：

• 我们设置当前众数为：res。初始化为数组第一元素。
• 设置当前票数和为：vote。初始化为0
• 遍历数组：如果票数和为0，更新众数为当前元素。
• 每次遍历，都对票数做统计，是众数，则+1，否则-1。

结果如下：

public int majorityElement(int[] nums) {
    int res = nums[0], vote = 0;
    for (int num : nums) {
        if (vote == 0) {
            res = num;
        }
        vote += (res == num) ? 1 : -1;
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10

二. 多数元素II

原题链接

在原题的基础上，不再是求出现次数超过2分之一的多数元素了。而是三分之一。即本题的返回个数最多有两个。

2.1 分析

我们这里这里假设：有两个（并且最多只有两个）符合题目条件的元素：x 和 y。他们的票数分别是v1 和 v2。

1. 利用摩尔投票法，确定两个候选数。因为我们这里假设的是2个都满足条件，但是实际情况可能只有一个或者没有。这里只是求得：出现次数最多的前两个数是哪几个（实际他们的出现次数却不知道）
2. 最后再对这两个候选人做计数统计，统计他们分别出现的次数是多少，是否满足题目要求。

阶段一：摩尔投票阶段，决定出现次数最多的前两个数：

// 初始化两个候选数和对应票数
int x = nums[0], y = nums[0];
int v1 = 0, v2 = 0;
// 摩尔投票，求得出现次数最多的两个数
for (int num : nums) {
    // 如果当前数和x一样
    if (x == num) {
        v1++;
        continue;
    }
    // 如果当前数和x一样
    if (y == num) {
        v2++;
        continue;
    }
    // 第一个候选票数为0了，那么当前数认定为第一个候选数
    if (v1 == 0) {
        x = num;
        v1++;
        continue;
    }
    // 第二个候选 同理
    if (v2 == 0) {
        y = num;
        v2++;
        continue;
    }
    // 否则，都不满足两个候选，两个候选的票数同时-1
    v1--;
    v2--;
}
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

这时候，我们拿到票数最多的两个元素，x和y。他们可能是同一个元素，也可能不是同一个元素。

接下来进入阶段二，统计票数阶段：

// 阶段二：统计票数阶段
v1 = 0;
v2 = 0;
for (int num : nums) {
    if (num == x) {
        v1++;
    } else if (num == y) {
        v2++;
    }
}
1
2
3
4
5
6
7
8
9
10

注意：不能这么写：（两个数如果是同一个，那就重复了）

for (int num : nums) {
    if (num == x) {
        v1++;
    }
    if (num == y) {
        v2++;
    }
}
1
2
3
4
5
6
7
8

最后，判断他们的出现次数是否满足条件，满足则加入结果集，所有代码如下：

public List<Integer> majorityElement(int[] nums) {
    ArrayList<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return res;
    }
    // 初始化两个候选数和对应票数
    int x = nums[0], y = nums[0];
    int v1 = 0, v2 = 0;
    // 摩尔投票，求得出现次数最多的两个数
    for (int num : nums) {
        // 如果当前数和x一样
        if (x == num) {
            v1++;
            continue;
        }
        // 如果当前数和x一样
        if (y == num) {
            v2++;
            continue;
        }
        // 第一个候选票数为0了，那么当前数认定为第一个候选数
        if (v1 == 0) {
            x = num;
            v1++;
            continue;
        }
        // 第二个候选 同理
        if (v2 == 0) {
            y = num;
            v2++;
            continue;
        }
        // 否则，都不满足两个候选，两个候选的票数同时-1
        v1--;
        v2--;
    }

    // 阶段二：统计票数阶段
    v1 = 0;
    v2 = 0;
    for (int num : nums) {
        if (num == x) {
            v1++;
        } else if (num == y) {
            v2++;
        }
    }
    // 最后看看是否超过了三分之一
    if (v1 > nums.length / 3) {
        res.add(x);
    }
    if (v2 > nums.length / 3) {
        res.add(y);
    }
    return res;
}
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
53
54
55
56