LeetCode 每日一题169: 求众数

LeetCode

今天依旧是一道简单难度的题, 但是问题的解决很巧妙. 拓展了一种新的解题思路

题目

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

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

示例 1:

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

示例 2:

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

---

思路

空间换时间

空间复杂度O(n), 时间复杂度O(n)

这是脑海里蹦出来的第一种做法, 以大数组或者键值对形式存储输入的值, 出现大于 n/2 的数值就返回对应的键即可.

然而如果你用 C 语言实现, 会发现鸡贼的 LeetCode 会出现爆内存错误提示, 这是因为标准的 C 语言函数库里面并没有 Map 这种键值对的形式, 这意味着你想用时间换空间的方式必须一次性申请一大块内存, 对于大一点的测试样例就直接爆掉了.因此这里只给出 C++ 的实现方式.

由于 LeetCode 后面提交了新的样例, 所以时间消耗从 12 ms 提到了 20 ms, 看看就好.

C++ 实现

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

result

Python 实现中最后的 Lambda 表达式意思是取字典中的项出来, 对字典的值求最大值, 然后取该值对应的键

Python实现

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = {}
        for i in nums:
            if i in result:
                result[i] += 1
            else:
                result[i] = 1
        return max(result.items(), key=lambda x:x[1])[0]

result

---

排序再求值

利用快速排序排序后再取最大值, 时间复杂度为 O(nlogn)

神奇的是不少同学利用 Python 内置的排序算法加上求最大值函数获得了超过了上面空间换时间算法的速度, Python 内置排序实现并不是很简单, 有时间可以展开讲, 但是如果真正笔试的时候, 这种解法是不可取的, 考官会让你自己实现排序, 这里不推荐, 看看就好.

当然, 如果实际项目中就随便用了, 写法简单易懂, 速度还很快.

Python实现

class Solution:
    def majorityElement(self, nums):
        nums.sort()
        return nums[len(nums)/2]

---

摩尔投票法

这就是今天想说的一种最巧妙的解法, 时间与空间复杂度均为最低(O(n) 和 O(l)). 做法来自于评论区的大佬.

这种做法的思路是从第一个数开始, 设count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数继续计数，总能找到最多的那个, 因为众数是出现次数大于 n/2 的.

C实现

int majorityElement(int* nums, int numsSize) {  
    int count = 1;
    int major = nums[0];
    for(int i = 1; i < numsSize; i ++){
        if(major == nums[i])
            count ++;
        else{
            count --;
            if(count == 0){
                major = nums[i+1];
            }     
        }
    }
    return major;
}

result

python实现

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = 0
        major = 0
        for i in nums:
            if count == 0:
                major = i
            if major == i:
                count += 1
            else:
                count -= 1
        return major

result