## 题目描述：

Given an integer array of size n, find all elements that appear more than` ⌊ n/3 ⌋ `times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?

## Python代码：

``````class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
n1 = n2 = None
c1 = c2 = 0
for num in nums:
if n1 == num:
c1 += 1
elif n2 == num:
c2 += 1
elif c1 == 0:
n1, c1 = num, 1
elif c2 == 0:
n2, c2 = num, 1
else:
c1, c2 = c1 - 1, c2 - 1
size = len(nums)
return [n for n in (n1, n2)
if n is not None and nums.count(n) > size / 3]
``````

Input: [2,2,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9] Output: [9] Expected: [9,3]

## 错误的Python代码：

``````class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
n1 = n2 = None
c1 = c2 = 0
for num in nums:
if n1 == num:
c1 += 1
elif n2 == num:
c2 += 1
elif c1 > c2:
n2, c2 = (n2, c2 - 1) if c2 > 1 else (num, 1)
else:
n1, c1 = (n1, c1 - 1) if c1 > 1 else (num, 1)
ans, size = [], len(nums)
if n1 is not None and sum([x == n1 for x in nums]) > size / 3:
ans.append(n1)
if n2 is not None and sum([x == n2 for x in nums]) > size / 3:
ans.append(n2)
return sorted(ans)
``````

Pingbacks已关闭。

1. Jie 发布于 2015年7月4日 01:21 #

Input:
[2,2,9,3,9,3,9,3,9,3,9,3,9,3,9,3,9]
Output:
[9]
Expected:
[9,3]

2. 在线疯狂 发布于 2015年7月4日 07:49 #

感谢指正！之前博文中的代码和思路是错误的，提交代码时LeetCode的测试样例中没有包含这样的反例，所以侥幸通过了系统测试，已经更正！

3. 若星汉天空 发布于 2016年5月6日 11:07 #

'''for num in nums:
if n1 == num:
c1 += 1
elif n2 == num:
c2 += 1
elif c1 == 0:
n1, c1 = num, 1
elif c2 == 0:
n2, c2 = num, 1
else:
c1, c2 = c1 - 1, c2 - 1'''
这段代码中，不知道楼主是否考虑过，当c1和c2同时为0的情况~~