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.
这一题可以用排序之后查看序列正中间那个元素的方法来解。但是复杂度是排序的复杂度nlog(n)。 用如下的方法借鉴Moore Voting。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
""" major = 0
count = 0 for x in nums:
if count == 0:
major = x
count = 1
elif x == major:
count += 1
else:
count -= 1 return major
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.
这一题由于对复杂度的限制是线性的，所以不能用排序。可以使用两个majority的candadite。
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return []
n1, n2, c1, c2 = 0, 1, 0, 0 for num in nums:
if num == n1:
c1 += 1
elif num == n2:
c2 += 1
elif c1 == 0:
n1 = num; c1 = 1
elif c2 == 0:
n2 = num; c2 = 1
else:
c1 -= 1; c2 -= 1
size = len(nums) return [n for n in (n1, n2) if nums.count(n) > size/3]