LeeCode上一道简单题引发的思考

  【前言】可能看过我之前博客的朋友会发现这期有点不一样,hhhh,我怎么成标题党了???没有,而是想通过这个LeeCode简单题(可能平常我们都不屑一顾)来深入思考一些东西,有兴趣的朋友可以继续看下去。


  【题目】169.多数元素

    题目描述:给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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


    示例:

    	示例 1:
    		输入: [3,2,3]
			输出: 3
 				  			 		
		示例 2:
			输入: [2,2,1,1,1,2,2]
			输出: 2

    思路一:如果有了解过list中count方法的朋友,头脑中可能第一个蹦出来的就是这个想法,因为这样只需要遍历列表,并对列表中每个值进行计数,当其大于n/2时就返回。于是就有了接下来的代码:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        sum_prices = 0  
        for i in range(1,len(prices)):
            if(prices[i]>prices[i-1]):  判断是否该买入
                sum_prices = sum_prices + prices[i]-prices[i-1]
            else:
                continue
        return sum_prices

    运行结果:
    LeeCode上一道简单题引发的思考
    最后的输入为[1,2,1,2…1,2,3,3,3,3,3,3,3…],想必看到这里,用count的朋友是不是发现了什么不对劲,不过这也引发了我接下来的想法。


    更进一步的思考:由于最近在学概率论,于是一个大胆的想法从我脑子里迸发出来,如果我们不是顺序输入index对应的值进行计数,而是采用随机的方式,那么从概率的角度上,我们只需要很少的次数就可以得到接近于1的结果,那这样可行吗?下面的试验开始了。

import random
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        sample_list = []
        for i in range(10):
            sample_list.append(random.randint(0,len(nums)-1))   #产生随机index
            if nums.count(nums[sample_list[i]]) >= len(nums)//2+1:  #采用count方法,对随机的index对应的值进行计数
                return nums[sample_list[i]]

    运行结果:
    LeeCode上一道简单题引发的思考

    你没看错,我们只产生了10次的随机数就得到了大于n/2的值,并且执行用时超过了99%的用户

    关于其中一些知识的链接:

    生成随机数的方法
    List count方法


    不过这样做虽然理论是可行的,但说起来未免有些投机取巧,那我们怎么去解这道题呢?


    思路二:那么此时,可能有部分朋友已经想到了利用哈希表来统计计数,本想自己手动实现该过程的,不过官方的一个解答又引起了我的兴趣,我们来看下他的代码:

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

作者:LeetCode
链接:https://leetcode-cn.com/problems/majority-element/solution/qiu-zhong-shu-by-leetcode-2/
来源:力扣(LeetCode)

    运行结果:
    LeeCode上一道简单题引发的思考
    大家关注到了其中的Counter方法吗?那他又和我们count方法有什么区别呢?为什么他又能在提交时击败将近80%的用户呢?由于我未找到内部实现的代码,因此只能有个大概的猜测,有知道的朋友可以在下方评论出来。

    思路三:接下来,我还要介绍一个有趣的算法,Boyer-Moore投票算法。他的原理是遍历整个数组,找到相同的数则加一,找到不同的数则减一,那么到最后剩下的为正值的数即众数,说通俗一些就是,某个大的团队投票给A,
剩下一些其他小团队都投给B,那么最终投票结果还是A,具体实现代码如下:

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ticikes_num = 0
        candidate = 0
        for num in nums:
            if ticikes_num==0:
                candidate = num  #标记候选人
                ticikes_num = ticikes_num+1
            else:   #进行投票过程
                if candidate==num:   
                    ticikes_num = ticikes_num+1
                else:
                    ticikes_num = ticikes_num-1
        return candidate

    运行结果:
    LeeCode上一道简单题引发的思考


    思路四:还有一些类似于分治思想、利用排序的方法等等解题思路,我会在下面分享官方的解题链接,如果你也有什么独特的解题方法也可以分享在下面。


    关于其中一些知识的链接:
    算法题解

    分享就到这里了,欢迎大家一起交流讨论。


    注明

    题目来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/majority-element

上一篇:[刷题] leecode记录


下一篇:【LeeCode】9. 回文数