LeetCode 169. Majority Element

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

分析

找出数组中的众数(出现次数大于数组长度一半)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):
# one pass + dictionary
def majorityElement(self, nums):
dic = {}
for num in nums:
if num not in dic:
dic[num] = 1
if dic[num] > len(nums)//2:
return num
else:
dic[num] += 1
# two pass + dictionary
def majorityElement1(self, nums):
dic = {}
for num in nums:
dic[num] = dic.get(num, 0) + 1
for num in nums:
if dic[num] > len(nums)//2:
return num
# Divide and Conquer
def majorityElement2(self, nums):
if not nums:
return None
if len(nums) == 1:
return nums[0]
a = self.majorityElement(nums[:len(nums)//2])
b = self.majorityElement(nums[len(nums)//2:])
if a == b:
return a
return [b, a][nums.count(a) > len(nums)//2]
def majorityElement3(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return sorted(nums)[len(nums)/2]

点评

一遍扫描+字典的做法,很容易理解,每次扫描的时候对出现的数 +1,然后判断是否大于 1