Problem: 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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution: Majority Element, Python:

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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-02-10 13:25:44
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @param num, a list of integers
# @return an integer
def majorityElement(self, num):
d = dict()
for item in num:
if item in d:
d[item] += 1
else:
d[item] = 1
return max(zip(d.values(), d.keys()))[1]

用字典(dict),按 value 取 key,时间复杂度 O(N)。在 OJ 上 AC 过了,但是还需要满足一个条件,即: max(zip(d.values(), d.keys()))[1] > len(num) // 2 .