多数元素系列问题

作者：Grey

原文地址：

博客园：多数元素系列问题

CSDN：多数元素系列问题

LeetCode 169. Majority Element

思路一：使用哈希表

很直接，就是把所有元素出现的次数存入哈希表，然后遍历一遍哈希表，就可以得到结果，代码略，虽然时间复杂度是O(N)，但是空间复杂度O(N)。

由于题目的follow-up要求空间复杂度O(1)，所以，这个方法其实并不是最优解。

思路二：一次删除两个不同的数

一次删除两个不同的数，如果存在majority element，那么这个数一定会最后剩下来，

但是，不能说一次删除两个不同的数，最后剩下了来的数就一定是majority element，

比如{1，2，3，4，5}这个数组，一次删除两个不同的数，最后剩下5，但是，5不是满足题目要求的值。

所以，在执行完每次删除两个不同的数这个操作后， 最后留下的数，还要过一遍数组，看下这个数是不是超过了半数，如果超过半数，才算是最后结果。

完整代码：

    public static int majorityElement(int[] arr) {
        int n = arr.length;
        int ans = arr[0];
        int hp = 1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == ans) {
                hp++;
                if (hp > n / 2) {
                    return arr[i];
                }
            } else {
                hp--;
                if (hp == 0) {
                    hp = 1;
                    ans = arr[i];
                }
            }
        }
        int count = 0;
        for (int e : arr) {
            if (e == ans) {
                count++;
            }
        }
        if (count > n / 2) {
            return ans;
        }
        return -1;
    }

说明：

其中hp标识候选数出现的次数，我们可以假设侯选数一开始就是arr[0]，所以hp的初始值是1，只要遍历到的数和候选数一致，hp++；如果不一致，hp--，如果hp变为0了，说明候选数字耗尽，重新设置侯选数为当前遍历到的数，直到遍历完毕，这样就实现了一次删除两个数的目的。

最后依据留下的数，去原始数组中找这个数出现的次数，如果真的大于n/2，则返回，否则，原始数组中不存在这样的数。

此外，这里有一个小的贪心，就是当hp已经到达数组一半以上的大小时候，直接返回当前的候选数（因为hp就表示侯选数出现的次数）。

LeetCode 229. Majority Element II

主要思路：一次性删掉三个不同的数

上一题是求超过n/2的数，本题是要求超过n/3的数，思路类似，对于上一题，我们的做法是一次性删除两个不同的数，这题，我们可以一次性删除三个不同的数，最后留下的数，再去遍历一遍数据统计其真实出现的次数是否超过n/3，即可。不过要注意：超过n/3的数，有可能没有，有可能有一个，也有可能有两个。但是不会是三个或者三个以上。

针对上一题，我们选择了一个hp来跟踪目标数的个数，针对这一题，我们需要设置两个hp来记录目标数的个数，因为超过n/3的数可能有两个。

到最后，还是要验证得到的数是否真的超过了n/3，只有真的超过n/3才加入结果中去。

完整代码见：

    public static List<Integer> majorityElement(int[] arr) {
        List<Integer> ans = new ArrayList<>();
        // 处理边界
        if (arr == null || arr.length == 0) {
            return ans;
        }
        // 处理边界
        if (arr.length == 1) {
            ans.add(arr[0]);
            return ans;
        }
        // 处理边界
        if (arr.length == 2) {
            ans.add(arr[0]);
            if (arr[0] != arr[1]) {
                ans.add(arr[1]);
            }
            return ans;
        }
        int n = arr.length;
        int hp1 = 0;
        int hp2 = 0;
        int v1 = arr[0];
        int v2 = arr[0];
        for (int e : arr) {
            if (e == v1) {
                hp1++;
            } else if (e == v2) {
                hp2++;
            } else if (hp1 == 0) {
                v1 = e;
                hp1 = 1;
            } else if (hp2 == 0) {
                v2 = e;
                hp2 = 1;
            } else {
                hp1--;
                hp2--;
            }
        }
        // 最后验证一下
        int n1 = 0;
        int n2 = 0;
        for (int e : arr) {
            if (e == v1) {
                n1++;
            } else if (e == v2) {
                n2++;
            }
        }
        if (n1 > n / 3) {
            ans.add(v1);
        }
        if (n2 > n / 3) {
            ans.add(v2);
        }
        return ans;
    }

牛客：在数组中找到出现次数大于n/k的数

主要思路：

根据上面两个题目的启发，要找到出现次数大于n/k的数，那就一次性删掉k个数，最后留下的数，验证一下个数是不是满足，即可。

原先需要设置hp来记录，这次，我们需要一个Hash表来登记k-1个数的hp量，空间复杂度可以做到O(k-1)。

 Map<Integer, Integer> map = new HashMap<>(k-1);

在遍历数组的过程中，记录每个数出现的次数，但是map严格要限制k-1个元素，

        Map<Integer, Integer> map = new HashMap<>(k - 1);
        for (int e : arr) {
            if (map.containsKey(e)) {
                map.put(e, map.get(e) + 1);
            } else {
                if (map.size() == k - 1) {
                    // 已经满了
                    LinkedList<Integer> removed = new LinkedList<>();
                    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                        if (entry.getValue() == 1) {
                            removed.add(entry.getValue());
                        }
                        map.put(entry.getKey(), entry.getValue() - 1);
                    }
                    for (int remove : removed) {
                        map.remove(remove);
                    }
                } else {
                    map.put(e, 1);
                }
            }
        }

在map里面的元素达到k-1的情况下，需要对里面的元素都操作-1，一旦有元素-1后变成了0，就要remove掉。

最后，把map中收集的元素再依次统计下次数，满足n/k的才最后加入结果集。

        int n = arr.length;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (times(arr, entry.getKey()) > n / k) {
                ans.add(entry.getKey());
            }
        }
        return ans;

其中times方法就是拿到这个元素真实出现的次数

    public static int times(int[] arr, int m) {
        int count = 0;
        for (int v : arr) {
            if (v == m) {
                count++;
            }
        }
        return count;
    }

完整代码见：

import java.util.*;

//  https://www.nowcoder.com/questionTerminal/4d448650c0324df08c40c614226026ad
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        List<Integer> ans = major2(arr, k);
        if (ans.isEmpty()) {
            System.out.println(-1);
        } else {
            for (int e : ans) {
                System.out.print(e + " ");
            }
        }
        in.close();
    }

    // 空间复杂度：O(K)
    // 推广到k
    public static List<Integer> major2(int[] arr, int k) {
        List<Integer> ans = new ArrayList<>();
        if (k < 2) {
            return ans;
        }
        Map<Integer, Integer> map = new HashMap<>(k - 1);
        for (int e : arr) {
            if (map.containsKey(e)) {
                map.put(e, map.get(e) + 1);
            } else {
                if (map.size() == k - 1) {
                    // 已经满了
                    LinkedList<Integer> removed = new LinkedList<>();
                    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                        if (entry.getValue() == 1) {
                            removed.add(entry.getValue());
                        }
                        map.put(entry.getKey(), entry.getValue() - 1);
                    }
                    for (int remove : removed) {
                        map.remove(remove);
                    }
                } else {
                    map.put(e, 1);
                }
            }
        }
        int n = arr.length;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (times(arr, entry.getKey()) > n / k) {
                ans.add(entry.getKey());
            }
        }
        return ans;
    }

    public static int times(int[] arr, int m) {
        int count = 0;
        for (int v : arr) {
            if (v == m) {
                count++;
            }
        }
        return count;
    }
}

更多

算法和数据结构笔记