给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
方法一：哈希统计
思路:我们用哈希统计数组中每个元素出现的次数，设数组的长度为n，返回所有统计次数超过⌊ n/3 ⌋的元素。
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
|
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
cnt = {}
ans = []
#给输入数组中的各个元素进行计数，cnt为字典
for v in nums:
if v in cnt:
cnt[v] += 1
else:
cnt[v] = 1
#判断出现次数
#" / "就一定表示 浮点数除法，返回浮点结果;" // "表示整数除法。
for item in cnt.keys():
if cnt[item] > len(nums)//3:
ans.append(item)
return ans
#test
s = Solution()
print(s.majorityElement([3,2,3]))
print(s.majorityElement(nums = [1]))
print(s.majorityElement([1,1,1,3,3,2,2,2]))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public List<Integer> majorityElement(int[] nums) {
HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (cnt.containsKey(nums[i])) {
cnt.put(nums[i], cnt.get(nums[i]) + 1);
} else {
cnt.put(nums[i], 1);
}
}
List<Integer> ans = new ArrayList<>();
for (int x : cnt.keySet()) {
if (cnt.get(x) > nums.length / 3) {
ans.add(x);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
unordered_map<int, int> cnt;
for (auto & v : nums) {
cnt[v]++;
}
for (auto & v : cnt) {
if (v.second > n / 3) {
ans.push_back(v.first);
}
}
return ans;
}
};
|
复杂度分析:
方法二：摩尔投票法
摩尔投票法：摩尔投票法的核心思想为对拼消耗。首先我们考虑最基本的摩尔投票问题，比如找出一组数字序列中出现次数大于总数1/2的数字（并且假设这个数字一定存在）。我们可以直接利用反证法证明这样的数字只可能有一个，摩尔投票算法的核心思想是基于这个事实。
每次从序列里选择两个不相同的数字删除掉（或称为「抵消」），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个元素。假设我们当前数组中存在次数大于总数一半的元素为 x，数组的总长度为 n，则我们可以把数组分为两部分，一部分为相同的 k 个元素 x，另一部分为 (n-k)/2 对个不同的元素配对，此时我们假设还存在另外一个次数大于总数一半的元素 y，则此时 y 因该满足 y > n/2 ，但是按照我们之前的推理 y 应当满足 y≤(n-k)/2 ，二者自相矛盾。
解题思路:题目要求找出其中所有出现超过⌊ n/3 ⌋次的元素。我们可以利用反证法推断出满足这样条件的元素最多只有两个，我们可以利用摩尔投票法的核心思想，每次选择三个互不相同的元素进行删除（或称为「抵消」）。我们可以假设数组中一定只存在一个次数大于 ⌊ n/3 ⌋的元素 x，其中 n 为数组的长度，则此时我们可以把数组分成两部分：一部分相同的 k 个元素 x，另一部分为(n-k)/3组三个不同的元素，我们知道三个不同的元素会被抵消，因此最终只会剩下一个元素为 x。如果只存在 2 个次数大于(n-k)/3的元素时，我们假设这两个不同的元素分别为 x 和 y，则此时我们一定可以把数组分成三部分：第一部分相同的 m 个元素 x，第二部分相同的 k 个元素 y，第三部分为 (n−m−k)/3组三个互不同的元素，我们知道三个互不同的元素会被抵消，因此最终只会剩下两个元素为 x 和 y。
- 我们每次检测当前元素是否为第一个选中的元素或者第二个选中的元素。
- 每次我们发现当前元素与已经选中的两个元素都不相同，则进行抵消一次。
- 如果存在最终选票大于 0 的元素，我们还需要再次统计已选中元素的次数,检查元素的次数是否大于 ⌊ n/3 ⌋ 。
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
|
class Solution:
def majorityElement(self, nums) :
ans = []
#用来记录被投票的人
element1, element2 = 0, 0
#记录被投票人的数值（不是得票数）
vote1, vote2 = 0, 0
for num in nums:
# 如果该元素为第一个元素，则计数加1
if vote1 > 0 and num == element1:
vote1 += 1
# 如果该元素为第二个元素，则计数加1
elif vote2 > 0 and num == element2:
vote2 += 1
# 选择第一个元素
elif vote1 == 0:
element1 = num
vote1 += 1
# 选择第二个元素
elif vote2 == 0:
element2 = num
vote2 += 1
# 如果三个元素均不相同，则相互抵消1次
else:
vote1 -= 1
vote2 -= 1
#用于统计可能候选人的得票数
cnt1, cnt2 = 0, 0
for num in nums:
if vote1 > 0 and num == element1:
cnt1 += 1
if vote2 > 0 and num == element2:
cnt2 += 1
# 检测元素出现的次数是否满足要求
if vote1 > 0 and cnt1 > len(nums) / 3:
ans.append(element1)
if vote2 > 0 and cnt2 > len(nums) / 3:
ans.append(element2)
return ans
|
复杂度分析
- 时间复杂度：O*(*n)，其中 n 为数组的长度。
- 空间复杂度：O(1)，只需要常数个元素用来存储关键元素和统计次数即可。
摩尔投票法理解：
摩尔投票法(Boyer–Moore majority vote algorithm)出自论文，算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为： o(n)，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行O(n^2)的时间。当选票有序时，可以很容易编出O(n)的程序，首先找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在O(n)时间内选出获票最多的，空间开销为O(1)。
会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。
在场的有个叫onwaier的，他很聪明，他想到一个方法。他用他那犀利人目光扫一遍所有代表们的选票，在脑子记住两件事，当前的候选人的名字cand和他对应的计数k（并不是他的选票数）。起始时，k的值为0，看每个人的选票时，先想想现在k是否为0，如果是0就将cand更新为他将看到的候选人的名字并且将k的值更新为1。观察每个人选票的过程，如果这个人的选票与cand相同，则将k的值加1；否则，将k的值减1。最后的cand可能胜选，还需统计他的总选票数是否超过一半。
算法演示
证明：假设共有n个代表（一人一票，选票总数为n）。当onwaier看到第i个代表的选票时( 1 ≤ i ≤ n )，前面他已经看到的所有选票可以分为两组，第一组是k个代表赞同cand；另一组是选票可以全部成对（选票不同）抵销。当处理完所有的选票时，如果存在大多数，则cand当选。假设存在一个x其不同于cand，但拥有的选票超过n/2。但因为第二组的选票可以全部成对抵销，所以x最多的选票数为(n−k)/2，因此x必须要收到第一组的选票才能超过一半，但是第一组的选票都是cand的，出现矛盾，假设不成立。所以，如果存在大多数，cand就是那个。
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
|
/*
根据多数元素出现的次数大于n/2且超过其它元素出现次数之和这一特点，进行统计
时间复杂度为：O(n)
空间复杂度为：O(1)
*/
int majorityElement(vector<int>& nums) {
int k = 0, cand = 0;
//成对抵销阶阶段
for(auto num:nums){
if(k == 0){
cand = num;
k = 1;
}
else{
if(num == cand){
++k;
}
else{
--k;
}
}
}
//计数阶段 判断cand的个数是否超过一半
k = 0;
for(auto num:nums){
if(num == cand){
++k;
}
}
if(k <= nums.size() / 2){
cand = -1;//表示未超过一半
}
return cand;
}
|
题2可以看成这样一个情形：一个班里要选副班长，至多2位。每一个投一票，成为副班长得票必须超过总票数的三分之一。
因为可能会产生两名。所以候选人cand与计数cnt都转成相应的数组形式cands与cnts，长度都为2。
第一阶段成对抵销时，cands[0]与cands[1]的选票不相互抵销，即如果代表将票投给了cands[0]，则cands[1]对应的cnts[1]的值不变化。投给cands[1]也是同样的道理。这样就转化成摩尔投票法的原始情形了。
第二阶段计数时，除了要判断两个候选的票数是否超过三分之一，还需判断两个候选是否相同。
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
57
58
59
60
61
62
63
|
/*
时间复杂度为：O(n)
空间复杂度为：O(1)
*/
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int len = nums.size();
vector<int>res, cands, cnts;
if(len == 0){//没有元素，直接返回空数组
return res;
}
cands.assign(2, nums[0]);
cnts.assign(2, 0);
//第1阶段 成对抵销
for(auto num: nums){
bool flag = false;
for(int i = 0; i < cands.size(); ++i){
if(num == cands[i]){
++cnts[i];
flag = true;
break;
}
}
if(!flag){
bool flag2 = false;
for(int j = 0; j < cands.size(); ++j){
if(cnts[j] == 0){
flag2 = true;
cands[j] = num;
cnts[j]++;
break;
}
}
if(!flag2){
for(int j = 0; j < cnts.size(); ++j){
--cnts[j];
}
}
}
}
//第2阶段 计数 数目要超过三分之一
cnts[0] = cnts[1] = 0;
if(cands[0] == cands[1])
cands.pop_back();
for(auto num:nums){
for(int i = 0; i < cands.size(); ++i){
if(cands[i] == num){
++cnts[i];
break;
}
}
}
for(int i = 0; i < cands.size(); ++i){
if(cnts[i] > len / 3){
res.push_back(cands[i]);
}
}
return res;
}
};
|
推广：至多选出m个代表，每个选票数大于n / (m + 1)，只需要将题2的判断最后候选是否相同代码进行修改即可。
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
|
class Solution {
public List<Integer> majorityElement(int[] nums) {
// 创建返回值
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
// 初始化两个候选人candidate，和他们的计票
int cand1 = nums[0], count1 = 0;
int cand2 = nums[0], count2 = 0;
// 摩尔投票法，分为两个阶段：配对阶段和计数阶段
// 配对阶段
for (int num : nums) {
// 投票
if (cand1 == num) {
count1++;
continue;
}
if (cand2 == num) {
count2++;
continue;
}
// 第1个候选人配对
if (count1 == 0) {
cand1 = num;
count1++;
continue;
}
// 第2个候选人配对
if (count2 == 0) {
cand2 = num;
count2++;
continue;
}
count1--;
count2--;
}
// 计数阶段
// 找到了两个候选人之后，需要确定票数是否满足大于 N/3
count1 = 0;
count2 = 0;
for (int num : nums) {
if (cand1 == num) count1++;
else if (cand2 == num) count2++;
}
if (count1 > nums.length / 3) res.add(cand1);
if (count2 > nums.length / 3) res.add(cand2);
return res;
}
}
|
如果至多选一个代表，那他的票数至少要超过一半（⌊ 1/2 ⌋）的票数；
如果至多选两个代表，那他们的票数至少要超过 ⌊ 1/3 ⌋ 的票数；
如果至多选m个代表，那他们的票数至少要超过 ⌊ 1/(m+1) ⌋ 的票数。
所以以后碰到这样的问题，而且要求达到线性的时间复杂度以及常量级的空间复杂度，直接套上摩尔投票法。
https://www.php.cn/python-tutorials-419658.html
https://blog.csdn.net/happyeveryday62/article/details/104136295