HOT100-13-多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

具体见题目详解。

算法思路

这个题目最麻烦的是题目要求：时间复杂度是O(n)，空间复杂度是O(1)，抛开这个不说，最容易想到的肯定是打hash表，统计每个数字出现的次数，当某个数字出现的次数大于n/2时(n为数组长度)，则表示找到了这个元素。在做这个题目之前一直在思考是使用map还是vector，因为map容易建立映射，不会受到nums[i]的影响，但是访问速率比较慢，通常是O(logn)；vector访问速度快，是O(1)，但是需要对负数特殊处理，通常是取nums[i] - min_num。但是实际测试下来vector会memory out，所以只能使用map，最好是unordered_map。代码可以看官方题解的，代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

时间复杂度是O(n)，空间复杂度是O(n)。

我想到的第二个方法就是排序再统计，算法思路大概是：

1. 先记录当前的数字为it，然后开始遍历。
2. 如果新的数字也是it，那么就让num++，当num > n / 2时，返回it。
3. 如果新的数字不是it，那么就记it为新的字母，同时让num充重置为1。
4. 在找到答案之前重复上述过程。

代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int standnum = nums.size() / 2;
        int it = nums[0];
        int tmpnum = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] != it) {
                tmpnum = 1;
                it = nums[i];
                continue;
            }
            tmpnum ++;
            if (tmpnum > standnum) {
                return it;
            }
        }
        return it;
    }
};

时间复杂度是O(nlogn)，空间复杂度是O(1)，没有用到多余的容器。运行结果如下：

达到题目要求的进阶做法我实在想不到，官方题解给出的感觉对我的机试或者面试或许帮助也不大，本来打算就此为止了，但是突然发现官方给出的排序思路更加牛逼！

我直接按照官方说的话来讲就是：对数组排序后，索引为n/2向上取整的元素必然是众数。这个很容易证明:

对于一个数组nums，如果一个数k为“众数”，即超过了n / 2，那么最极端的两种情况就是其分别位于最左端开始和最右端结束，即使这样，因为k超过了n / 2个，那么0 + n / 2和 n - n / 2处也必然是k。

所以我们的排序计数可以直接简化为排序即可，返回n / 2处的元素。代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

时间复杂度是O(logn)，空间复杂度是O(1)，效果就不看了，其实差不多。