要了解，摩尔投票，首先看一道题目
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-majority-element-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解：
思路一：哈希表存储
拿到此题，第一反应是遍历数组，用HashMap存储每个元素出现的次数，如果次数 > 一半时，返回。 遍历完毕，都没有元素数量 > half。 则没有主要元素，返回 -1.
- 时间复杂度 : O(N)
- 空间复杂度 : O(M)
代码如下：
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
|
/*
*
* 这道题第一反应是遍历数组
* 用map存储每个数字出现的次数
*
* 当 次数 > half时， 则为主要元素
* 遍历到 最终，没有 > half 的， return -1
*
* 时间复杂度 : O(n)
* 空间复杂度 : O(n)
*
* 但是，明显不符合题目要求
* 题目中要求 时间:O(N), 空间O(1)
*
* 接下来，我们尝试使用 O(1) 的空间复杂度解决
* */
HashMap<Integer,Integer> map = new HashMap<>();
public int majorityElement(int[] nums) {
int count = nums.length;
int half = (count >> 1);
for (int i = 0; i < count; i++) {
int cnt = map.getOrDefault(nums[i], 0);
if (++cnt > half) return nums[i];
map.put(nums[i], cnt);
}
return -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
|
// 分治策略
// 分别计算 左右的众数
// 如果左右众数一样， 则为最终结果
// 如果不一样， 则分别在左右计算，众数出现次数。出现次数多者为最终结果
public int majorityElement1(int[] nums){
return majority(nums, 0, nums.length);
}
public int majority(int[] nums, int begain , int end){
if (end - begain < 2) return nums[begain];
int mid = (begain + end) >> 1;
int left = majority(nums, begain, mid);
int right = majority(nums, mid, end);
if (left == right) return left;
int lcnt = countInRange(nums,left,begain,end);
int rcnt = countInRange(nums,right,begain,end);
return lcnt > rcnt ? left : right;
}
public int countInRange(int[] nums, int num, int begain , int end){
int count = 0;
for (int i = begain; i < end; i++) {
if (nums[i] == num) count ++;
}
return count;
}
|
思路三:
说明：
你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？
显然以上解题，不符合要求。 用到了额外的哈希表存储，空间复杂度为 O(N)
分治策略，也用到了额外 O(logN) 的栈空间
接下来引入我们这篇文章主要讲的,摩尔投票
摩尔投票
什么是摩尔投票算法？
摩尔投票算法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数字抵消， 最终剩下的就是要找的那个数。
知乎一哥们，非常形象的解释了这个问题。
这样一来，摩尔投票就非常好理解了。 不相同的数字抵消， 最终剩余的数字一定是最多的。 如果次数超过half， 则为最终结果。
如果次数不超过half， 则没有主要元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// 摩尔投票
public int majorityElement2(int[] nums) {
int count = 1;
int tmp = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] != tmp){
count --;
if (count < 0){
count = 1;
tmp = nums[i];
}
}else {
count ++;
}
}
return count > 0 ? tmp : -1;
}
|
