【前言】可能看过我之前博客的朋友会发现这期有点不一样，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:continuereturn sum_prices

    运行结果：
  
  最后的输入为[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))   #产生随机indexif nums.count(nums[sample_list[i]]) >= len(nums)//2+1:  #采用count方法，对随机的index对应的值进行计数return nums[sample_list[i]]

    运行结果：
  

    你没看错，我们只产生了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）

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

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

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

    运行结果：
  


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

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

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

    注明：

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