【前言】可能看过我之前博客的朋友会发现这期有点不一样，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
运行结果：
最后的输入为[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]]
运行结果：
你没看错，我们只产生了10次的随机数就得到了大于n/2的值，并且执行用时超过了99%的用户
关于其中一些知识的链接：
不过这样做虽然理论是可行的，但说起来未免有些投机取巧，那我们怎么去解这道题呢？
思路二:那么此时，可能有部分朋友已经想到了利用哈希表来统计计数，本想自己手动实现该过程的，不过官方的一个解答又引起了我的兴趣，我们来看下他的代码：
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 = 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
运行结果：
思路四：还有一些类似于分治思想、利用排序的方法等等解题思路，我会在下面分享官方的解题链接，如果你也有什么独特的解题方法也可以分享在下面。
关于其中一些知识的链接：
算法题解
分享就到这里了，欢迎大家一起交流讨论。
注明：
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element