🚩[LeetCode]Ar169. 多数元素

🚩传送门：https://leetcode-cn.com/problems/majority-element/

题目

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3] 输出：3

示例 2：

输入：[2,2,1,1,1,2,2] 输出：2

📖 文字题解

说明最简单的暴力方法是，枚举数组中的每个元素，再遍历一遍数组统计其出现次数。该方法的时间复杂度是 ，会超出时间限制，因此我们需要找出时间复杂度小于 的优秀做法。

解题思路一：哈希表

我们知道出现次数最多的元素大于 次，所以可以用哈希表来快速统计每个元素出现的次数。

复杂度分析

时间复杂度：，其中 为数组 长度。

我们遍历数组 一次，对于 中的每一个元素，将其插入哈希表都只需要 常数 时间。如果在遍历时没有维护最大值，在遍历结束后还需要对哈希表进行遍历，因为哈希表中占用的空间为 （可参考下文的空间复杂度分析），那么遍历的时间不会超过 。因此总时间复杂度为 。

空间复杂度：。

哈希表最多包含 个键值对，所以占用的空间为 。这是因为任意一个长度为 的数组最多只能包含 个不同的值，但题中保证 数组一定有一个众数，会占用（最少） 个数字。因此最多有 个不同的其他数字，所以最多有 个不同的元素。

官方代码

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        //创建counts的map
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            //未出现置1
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            } else {
                //出现次数增加
                counts.put(num, counts.get(num) + 1);
            }
        }
        return counts;
    }
    public int majorityElement(int[] nums) {
        //计算每个数字的个数
        Map<Integer, Integer> counts = countNums(nums);
        Map.Entry<Integer, Integer> majorityEntry = null;
        //便利整个EntrySet找出最大值
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }
        return majorityEntry.getKey();
    }
}

解题思路二：排序

如果将数组 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 的元素（下标从 0 开始）一定是众数。

对于这种算法，我们先将 数组排序，然后返回上文所说的下标对应的元素。

下图解释了为什么这种策略是有效的。第一个例子是 为奇数的情况，第二个例子是 为偶数的情况。

复杂度分析

时间复杂度：

其中 为数组长度，将数组排序的时间复杂度为 。

空间复杂度：。

如果使用语言自带的排序算法，需要使用 的栈空间。如果自己编写堆排序，则只需要使用 的额外空间。

官方代码

class Solution {    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

解题思路三：随机化

因为超过 数组下标被众数占据，这样我们随机挑选一个下标对应的元素并验证，有很大的概率找到众数。

复杂度分析

时间复杂度：理论上最坏情况下的时间复杂度为

因为如果我们的运气很差，这个算法会一直找不到众数，随机挑选无穷多次，所以最坏时间复杂度是没有上限的。然而，运行的期望时间是线性的。

为了更简单地分析，先说服你自己：由于众数占据 超过 数组一半的位置，期望的随机次数会小于众数占据数组恰好一半的情况。因此，我们可以计算随机的期望次数：

（下标为 prob 为原问题，mod 为众数恰好占据数组一半数目的问题）

计算方法为：当众数恰好占据数组的一半时，第一次随机我们有 的概率找到众数，如果没有找到，则第二次随机时，包含上一次我们有 的概率找到众数，以此类推。因此期望的次数为 的和，可以计算出这个和为 2，说明期望的随机次数是 常数 。每一次随机后，我们需要 的时间判断这个数是否为众数，因此期望的时间复杂度为 。

空间复杂度：。随机方法只需要常数级别的额外空间。

官方代码

class Solution {
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }
    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }
    public int majorityElement(int[] nums) {
        Random rand = new Random();
        int majorityCount = nums.length / 2;
        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];
            if (countOccurences(nums, candidate) > majorityCount) {
                return candidate;
            }
        }
    }
}

解题思路四：分治

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。

使用反证法来证明这个结论

假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数 ≤ left / 2 + right / 2 次，其中 left 和 right 分别是左半部分和右半部分的长度。 由于 left / 2 + right / 2 <= (left + right) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。

这样以来，我们就可以使用分治法解决这个问题：将数组分成左右两部分，分别求出左半部分的众数 以及右半部分的众数 ，随后在 和 中选出正确的众数。

我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。

1. 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。

2. 如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。

   • 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。

   • 否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。

     官方代码

     class Solution {
     private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
     }
     private int majorityElementRec(int[] nums, int lo, int hi) {
        // base case; the only element in an array of size 1 is the majority
        // element.
        if (lo == hi) {
            return nums[lo];
        }
        // recurse on left and right halves of this slice.
        int mid = (hi - lo) / 2 + lo;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);
        // if the two halves agree on the majority element, return it.
        if (left == right) {
            return left;
        }
        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);
        return leftCount > rightCount ? left : right;
     }
     public int majorityElement(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
     }
     }

解题思路五：Boyer-Moore 投票算法

如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

1. 维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 为首元素，count 为 0；
2. 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，随后我们判断 x：
   • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
   • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
3. 在遍历完成后，candidate 即为整个数组的众数。

Boyer-Moore 算法的正确性较难证明，这里给出一种较为详细的用例子辅助证明的思路，供读者参考：

1. 首先根据算法步骤中对 count 的定义，可以发现：在对整个数组进行遍历的过程中，**count **的值一定非负。这是因为如果 count的值为 0，那么在这一轮遍历的开始时刻，我们会将 x 的值赋予candidate并在接下来的一步中将 count的值增加 1。因此 count的值在遍历的过程中一直保持非负。

那么 count 本身除了计数器之外，还有什么更深层次的意义呢？
作为例子，首先写下它在每一步遍历时 candidate 和 count 的值：

nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7 count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4

我们再定义一个变量 value，它和真正的众数 maj 绑定。在每一步遍历时，如果当前的数 x 和 maj 相等，那么 value 的值加 1，否则减 1。 **value** 的实际意义即为：到当前的这一步遍历为止，众数出现的次数比非众数多出了多少次。

我们将 value 的值也写在下方： nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7] count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4 value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4

有没有发现什么？ 发现在每一步遍历中，count 和 value 要么相等，要么互为相反数！

1. 在候选众数 candidate 就是 maj 时，它们相等，
2. candidate 是其它的数时，它们互为相反数！

为什么会有这么奇妙的性质呢？ 这并不难证明：我们将候选众数 candidate 保持不变的连续的遍历称为「一段」。在同一段中，count 的值是根据 candidate == x 的判断进行加减的。

1. 那么如果 candidate 恰好为 maj，那么在这一段中，count 和 value 的变化是同步的；
2. 如果 candidate 不为 maj，那么在这一段中 count 和 value 的变化是相反的。

因此就有了这样一个奇妙的性质。

这样以来，由于：

1. 我们证明了 count 的值一直为非负，在最后一步遍历结束后也是如此；
2. 由于 value 的值与真正的众数 maj 绑定，并且它表示「众数出现的次数比非众数多出了多少次」，那么在最后一步遍历结束后，value 的值为正数；

在最后一步遍历结束后，count 非负，value 为正数，所以它们不可能互为相反数，即 count == value。因此在最后「一段」中，count 的 value 的变化是同步的，也就是说，candidate 中存储的候选众数就是真正的众数 maj。

复杂度分析

时间复杂度：。 算法只对数组进行了一次遍历。

空间复杂度：。算法只需要常数级别的额外空间。

官方代码

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}