摩尔投票法和大多数

介绍

摩尔投票法(Majority Vote Alogrithm)是一种在线性时间O(n)和空间复杂度的情况下，在一个元素序列中查找包含最多的元素。

应用场景

给定一个int数组，求数组中个数超过1/2（m/n）的数。

算法优势

可以做到时间复杂度o(n), 空间复杂度o(1)。

核心思想

同加，异减。

做法

每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

典型例题(来自LeetCode)

一、摩尔投票算法的经典例题

 169. Majority Element

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.

解释：
题目大意是给定一个长度为n的数组，找出出现次数大于1/2的数。

思路：
出现次数大于1/2的数只能是一个。那么，我们用两个int变量major、cnt分别记录候选众数和其出现的次数。在每一轮投票过程中，从数组中找出一对不同的元素，将其从数组中删除。这样不断的删除直到无法再进行投票，如果数组为空，则没有任何元素出现的次数超过该数组长度的一半。如果只存在一种元素，那么这个元素为目标元素。Java代码如下：

 1class Solution {
 2    public int majorityElement(int[] nums) {
 3        int major = nums[0];
 4        int cnt = 0;
 5        for (int i = 0; i < nums.length; i++) {
 6            if (cnt == 0) {
 7                major = nums[i];
 8                cnt++;
 9            } else if (nums[i] == res) {
10                cnt++;
11            } else
12                cnt--;
13        }
14       return major;
15    }
16}

二、摩尔投票算法的改进例题

229. Majority Element II

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.

思路：
出现次数大于1/3的数最多只能是2个。我们用4个变量来记录，m1, m2为候选众数，c1, c2为它们对应的出现次数。
遍历数组，记当前数字为num,若num与n1或n2相同，则将其对应的出现次数加1,否则，若c1或c2为0，则将其置为1，对应的候选众数置为num.否则，将c1与c2分别减1。
最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。Java代码如下：

 1class Solution { 
 2    public List<Integer> majorityElement(int[] nums) {
 3        List<Integer> res = new ArrayList<>();
 4        if(nums == null || nums.length == 0) return res;
 5        if(nums.length == 1) {
 6            res.add(nums[0]);
 7            return res;
 8        }
 9        int m1 = nums[0];
10        int m2 = 0;
11        int c1 = 1;
12        int c2 = 0;
13        for(int i=1; i<nums.length; i++) {
14            int x = nums[i];
15            if(x == m1) ++c1;
16            else if(x == m2) ++c2;
17            else if(c1 == 0) {
18                m1 = x;
19                c1 = 1;
20            } else if(c2 == 0) {
21                m2 = x;
22                c2 = 1;
23            } else {
24                --c1; --c2;
25            }
26        }
27        c1 = 0; c2 = 0;
28        for(int i = 0; i < nums.length; i++) {
29            if(m1 == nums[i]) ++c1;
30            else if(m2 == nums[i]) ++c2;
31        }
32        // 得到的数不一定个数大于总长度的1/3，所以要验证！
33        if(c1 > nums.length / 3) res.add(m1);
34        if(c2 > nums.length / 3) res.add(m2);
35        return res;
36    }
37}