day13 多数元素

Easy 说是，希望能搞快点。

读题

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

• n == nums.length
• 1 <= n <= 5 * 104
• -10^9 <= nums[i] <= 10^9

进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

不进阶的话，遍历呗，数值范围都给出来了。记录每个元素出现次数，如果有大于 n/2 的就返回。但是 nums 元素的范围很大，到 10^9 去了，通过一个长 10^9×2 的数组保存范围内每个数字出现的次数显然是不现实的。不过可以使用 map，int 对应 int 的 map。
总之有代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> nums_map;
        int n = nums.size();
        for(int i=0;i<n;i++){
            nums_map[nums[i]]+=1;
            if(nums_map[nums[i]]>n/2) {
                return nums[i];
            }
        }
        return 0;
    }
};

结果

0 ms，27.56 MB 内存，不错。

官方题解

官方题解说有 O(n^2) 的暴力解法，枚举各个元素，然后遍历数组统计其出现次数。
这也太暴力了。

方法一：哈希表

确实使用的了哈希表来统计每个元素出现的次数，不过是取了出现的最大次数，而不是像我一样直接返回了。
值得注意的是，哈希表的空间复杂度是 O(n) 而非要求的 O(1)。

方法二：排序

基于这么一个思想：
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n​/2 的元素（下标从 0 开始）一定是众数。
这是基于题目所给出的前提条件必定有元素出现次数 大于 ⌊ n/2 ⌋ 才成立的，个人认为不具有普适价值。

方法三：随机化

题解言：
因为超过 n​/2 的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数。
感觉类似于所谓猴子排序，但是不一样的是不需要排序，而是在数量大于 n/2 时停止并返回即可。这种做法最坏情况下是永远也找不到，一直卡住，但是概率很低，期望运行时间是 n。

方法四：分治

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数。
仍然是基于出现次数 大于 ⌊ n/2 ⌋ 的元素为众数这个前提的。

方法五：Boyer-Moore 投票算法

怎么还有？
如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
这个方法时间空间复杂度都是上述方法里最小的，看似花哨，实则非常实用，而且正确。

收获

这题有很多方法，不过其中有三种都是基于有众数出现次数大于 n/2 这个前提的。乍一看都是非常狭隘的、仅仅针对这一题的方法，转念一想，或许是因为是基础问题，所以被研究得多？
其中的随机化、分治、Boyer-Moore 投票算法我都是没有接触过的，看看日后其他题目是否会用上。