专栏首页程序员的碎碎念LeetCode 每日一题169: 求众数

LeetCode 每日一题169: 求众数

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

题目

给定一个大小为 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;
    }
};

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]

排序再求值

利用快速排序排序后再取最大值, 时间复杂度为 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;
}

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

本文分享自微信公众号 - 程序员的碎碎念(gh_53e607dd4782)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode力扣算法题目——四数的和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    benny
  • LeetCode每日一题53: 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    benny
  • php实现登录短信验证

    今天benny要跟大家说这个其实很简单,就是借用某一个平台的短信api接口实现短信验证,说简单呢,那是因为他的官网:http://www.ucpaas....

    benny
  • leetcode-169-Majority Element

    chenjx85
  • LeetCode 31. Next Permutation

    ShenduCC
  • LeetCode 307. Range Sum Query - Mutable

    ShenduCC
  • LeetCode 324. 摆动排序 II

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

    Michael阿明
  • LeetCode51|寻找旋转排序数组中的最小值

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    后端Coder
  • LeetCode第六天

    第六天 30.(219) Contains Duplicate II ? JAVA class Solution { public boolean co...

    郭耀华
  • Array - 164. Maximum Gap

    Given an unsorted array, find the maximum difference between the successive elem...

    用户5705150

扫码关注云+社区

领取腾讯云代金券