Majority Vote总结
Majority Element题型是找一个数组中超过n/k的majority元素,使用的算法是Majority Vote。
原理就是对于每一个Majority Element都设置一个count:1.如果选中的num与Majority Element相等,对应的count++ 2.如果所有的Majority Element没有与num相等的,那么去检查有没有count为0,如果有,将这个Majority Element设置为num并将count设为1 3.如果以上都不符合,那么所有count–
所以我们看到程序中都是用的if,else if,也就是说有符合条件的情况,对于这个num的判断就结束了
Majority Element
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/*
169. Majority Element
Easy
2074
181
Favorite
Share
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2
*/
class Solution {
public int majorityElement(int[] nums) {
int majority = 0;
int count = 0;
for(int i = 0;i<=nums.length-1;i++){
if(nums[i]==majority){
count++;
}
else if(count==0){
majority = nums[i];
count++;
}
else {
count--;
}
}
return majority;
}
}Majority Element II
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78/*
229. Majority Element II
Medium
1081
125
Favorite
Share
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
*/
class Solution {
public List<Integer> majorityElement(int[] nums) {
int majority1 = 0;
int majority2 = 0;
int count1 = 0;
int count2 = 0;
for(int i = 0;i<=nums.length-1;i++){
//先判断是否有Majority等于nums[i]
if(nums[i] == majority1){
count1++;
}
else if(nums[i] == majority2){
count2++;
}
//再判断是否有count为0
//先后顺序不能变,不能先判断count是否为0,因为可能有一个majority的count是0,但另一个不是0,那么他还可能等于nums[i]
else if(count1==0){
majority1 = nums[i];
count1++;
}
else if(count2==0){
majority2 = nums[i];
count2++;
}
//都不符合的话count都减1
else {
count1--;
count2--;
}
}
List<Integer> l = new LinkedList<>();
count1 = 0;
count2 = 0;
for(int num:nums){
if(num==majority1){
count1++;
}
else if(num==majority2){
count2++;
}
}
if(count1>nums.length/3){
l.add(majority1);
}
if(count2>nums.length/3){
l.add(majority2);
}
return l;
}
}