这道题首先是受到 169 Majority Element 的启发 （https://en.wikipedia.org/wiki/Boyer-Moore_Majority_Vote_Algorithm） 知道最多有2个可能的数满足条件。 而这道题不同的是无法确定是否存在， 因此得到可能的candidates后需要重新扫描一遍数组 判定是否满足条件， 代码如下 时间 104ms
import math class Solution: # @param {integer[]} nums # @return {integer[]} def majorityElement(self, nums): if nums == []: return [] x, cx, y, cy = None, 0, None, 0 i = 0 while i < len(nums): n = nums[i] if x == None and y == None: x, cx = n, 1 elif x == None: if y == n: cy += 1 else: x, cx = n,1 elif y == None: if x == n: cx += 1 else: y, cy = n,1 else: if x == n: cx += 1 elif y == n: cy += 1 else: cx -= 1 cy -= 1 if cx == 0: x = None if cy == 0: y = None i += 1 can = [] ans = [] if x != None: can.append(x) if y != None: can.append(y) for a in can: c = 0 for n in nums: if a == n: c += 1 if c > math.floor(len(nums)/3): ans.append(a) return ans
觉得代码写的不够简练， 查询了后知道 collections下有一个defaultdict, 试着使用， 并且在最后扫描是 使用 lambda来简化代码 运行时间 76ms 有明显改善 代码如下
from collections import defaultdict class Solution: # @param {integer[]} nums # @return {integer[]} def majorityElement(self, nums): dic = defaultdict(int) for n in nums: if n in dic: dic[n] += 1 else: if len(dic) < 2: dic[n] += 1 else: for k in dic.keys(): dic[k] -= 1 if dic[k] == 0: del dic[k] ans = [] for k in dic.keys(): if len(filter(lambda x: x == k, nums)) > len(nums) / 3: ans.append(k) return ans
原文：http://www.cnblogs.com/dapanshe/p/4625724.html