[数据结构与算法]leetcode 229. 求众数 II

2021.10.22 每日一题
今天有两道类似的题目

1、 169. 多数元素

思路
①摩尔投票法: 适用于找出一堆数字中出现次数大于1/n的数字

public class Solution {

    public int majorityElement(int[] nums) {
        int count = 0 , candidate = 0;

        for (int n : nums) {
            if(0 == count)
                candidate = n;
            count += candidate == n ? 1 : -1 ;
        }
        return candidate;
    }
}

②哈希表 注意哈希表的遍历方法

public class Solution {

    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> counts = new HashMap<>();

        for (int n : nums) {
            if (counts.containsKey(n))
                counts.put(n, counts.get(n) + 1);
            else
                counts.put(n, 1);
        }

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (null == majorityEntry || majorityEntry.getValue() < entry.getValue())
                majorityEntry = entry;
        }

        return majorityEntry.getKey();
    }

}

值得一提的是，此题还有分治做法，既然是众数，那么分开后一定是左右两边其中一边的众数，那么我们把他分成两半，如果长度是1，那就返回自己，合并时如果左右两边数字不等，那就返回多的一部分(如果数目一样，那随便返回哪个都可，因为此时这两个数字都不是众数);如果相等，那就返回一样的数。

2、229. 求众数 II

思路 同样的是摩尔投票法，不过情况复杂了一些，大概有五种

遍历数组，设当前元素为n，用两个变量(candidate1 candadate2)记录可能是众数的数字，用vote1 vote2记录他们出现的次数
之可能存在以下五种情况

①如果 vote1 == 0 那就令candidate1 = n,且vote1++
②如果 vote2 == 0 那就令candidate2 = n,且vote2++
③如果 n == candidate1 ,那么vote1++
④如果 n == candidate2 ,那么vote2++
⑤如果 n都不等,那么vote1-- vote2–

注意

判断五种情况的顺序问题
注意具体判断顺序应该颠倒为③④①②⑤，因为如果①②在前，会带来两个问题
①对于输入为[1,1,2],candidate1和candidate2存储的值就会相同
②必须要先判断③④，否则如果在遍历过程中，vote1 == 0 但是 n == vote2 ，那么此时执行的就是把n赋给vote1，所以必须要先判断n和两个候选人是否相等

最后还要进行一次遍历 用于判断次数是否合适
因为在我们第一次遍历完，vote1和vote2并不是真正出现的次数，所以还要再次遍历，找到真正的次数，至于为什么要判断，因为有可能有些元素运气好，比如[1,1,1,2,3,5],那么在遍历完了之后candidate2是5，但是5并不是真正的众数，所以还需要再次遍历，确定真正的出现次数

在最后一次遍历前 vote == 0的candidate出现次数一定小于1/3

class Solution {
public List<Integer> majorityElement(int[] nums) {

        Integer candidate1 = null, candidate2 = null;
        int vote1 = 0, vote2 = 0;

        for (int n : nums) {

            if (vote1 > 0 && candidate1 == n)
                vote1++;
            else if (vote2 > 0 && candidate2 == n)
                vote2++;
            else if (0 == vote1) {
                vote1++;
                candidate1 = n;
            } else if (0 == vote2) {
                vote2++;
                candidate2 = n;
            } else {
                vote1--;
                vote2--;
            }
        }

        int count1 = 0, count2 = 0;
        for (int n : nums) {
            if (vote1 > 0 && candidate1 == n)
                count1++;
            if (vote2 > 0 && candidate2 == n)
                count2++;
        }

        ArrayList<Integer> result = new ArrayList<Integer>();

        if (vote1 > 0 && count1 > nums.length / 3)
            result.add(candidate1);
        if (vote2 > 0 && count2 > nums.length / 3)
            result.add(candidate2);

        return result;
    }
}

值得注意的是，摩尔投票法可以用于找出n个元素中k-1个出现次数超过1/k的数，一般思路为
①申请k-1个candidate,k-1个vote
②一次遍历，讨论多种情况
③二次遍历，确定每个次数