上一篇:算法随笔_64: 含特定字母的最小子序列-CSDN博客
=====
题目描述如下:
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
=====
算法思路:
我们可以利用字典来统计每种元素出现的次数。最后再遍历一遍字典，即可找出大于n/2的元素。
时间复杂度O(n)。下面是Python代码实现:
class Solution(object):def majorityElement(self, nums):""":type nums: List[int]:rtype: int"""num2cnt={}for num in nums:if num not in num2cnt:num2cnt[num]=0num2cnt[num]+=1res=0n_2=len(nums)/2for num in num2cnt:if num2cnt[num]>n_2:res=numbreakreturn res
