LeetCode 169 I

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

Solution

参考https://www.cnblogs.com/grandyang/p/4233501.html

1. Moore Voting，需要 O(n) 的时间和 O(1) 的空间，比Hashmap更好。
2. 这种投票法先将第一个数字假设为过半数，然后把计数器设为1，比较下一个数和此数是否相等，若相等则计数器加一，反之减一。然后看此时计数器的值，若为零，则将下一个值设为候选过半数。以此类推直到遍历完整个数组，当前候选过半数即为该数组的过半数。
3. 不仔细弄懂摩尔投票法的精髓的话，过一阵子还是会忘记的，首先要明确的是这个叼炸天的方法是有前提的，就是数组中一定要有过半数的存在才能使用，下面我们来看本算法的思路，

• 这是一种先假设候选者，然后再进行验证的算法。我们现将数组中的第一个数假设为过半数，然后进行统计其出现的次数，如果遇到同样的数，则计数器自增1，否则计数器自减1，如果计数器减到了0，则更换下一个数字为候选者。
• 这是一个很巧妙的设定，也是本算法的精髓所在，为啥遇到不同的要计数器减1呢，为啥减到0了又要更换候选者呢？
• 首先是有那个强大的前提存在，一定会有一个出现超过半数的数字存在，那么如果计数器减到0了话，说明目前不是候选者数字的个数已经跟候选者的出现个数相同了，那么这个候选者已经很weak，不一定能出现超过半数，我们选择更换当前的候选者。
• 那有可能你会有疑问，那万一后面又大量的出现了之前的候选者怎么办，不需要担心，如果之前的候选者在后面大量出现的话，其又会重新变为候选者，直到最终验证成为正确的过半数

LeetCode 229 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.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution

参考： https://www.cnblogs.com/grandyang/p/4606822.html

这道题让我们求出现次数大于 n/3 的数字，而且限定了时间和空间复杂度，那么就不能排序，也不能使用 HashMap，这么苛刻的限制条件只有一种方法能解了，那就是摩尔投票法 Moore Voting，这种方法在之前那道题 Majority Element 中也使用了。题目中给了一条很重要的提示，让我们先考虑可能会有多少个这样的数字，经过举了很多例子分析得出，任意一个数组出现次数大于 n/3 的数最多有两个，具体的证明我就不会了，我也不是数学专业的（热心网友用手走路提供了证明：如果有超过两个，也就是至少三个数字满足“出现的次数大于 n/3”，那么就意味着数组里总共有超过 3*(n/3) = n 个数字，这与已知的数组大小矛盾，所以，只可能有两个或者更少）。那么有了这个信息，我们使用投票法的核心是找出两个候选数进行投票，需要两遍遍历，第一遍历找出两个候选数，第二遍遍历重新投票验证这两个候选数是否为符合题意的数即可，选候选数方法和前面那篇 Majority Element 一样，由于之前那题题目中限定了一定会有大多数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的大多数可能不存在，所以要有验证。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<> ();
        if (nums == null || nums.length == 0)
            return result;
        
        int candidate1 = 0;
        int count1 = 0;
        
        int candidate2 = 0;
        int count2 = 0;
        
        for (int num : nums) {
            if (num == candidate1) {
                count1 ++;
                continue;
            }
            
            if (num == candidate2) {
                count2 ++;
                continue;
            }
                
            if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
                continue;
            }
            
            if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
                continue;
            }
            
            count1 --;
            count2 --;
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int num : nums) {
            if (num == candidate1)
                count1++;
            
            else if (num == candidate2)
                count2++;
        }
        
        if (count1 > nums.length / 3) {
            result.add (candidate1);
        }
        
        if (count2 > nums.length / 3) {
            result.add (candidate2);
        }
        
        return result;
    }
}