169. 多数元素（简单）-LeetCode

题目描述

自己解法

第一种：哈希表统计

class Solution: def majorityElement(self, nums: List[int]) -> int: ValCount = dict() ans = 0 for val in nums: if val in ValCount: ValCount[val] += 1 else: ValCount[val] = 1 for key,value in ValCount.items(): if value > len(nums) // 2: ans = key return ans

时间复杂度$O(n)$，空间复杂度$O(n)$ 第二种：摩尔投票法

class Solution: def majorityElement(self, nums: List[int]) -> int: major = None count = 1 for val in nums: if major == val: count += 1 else: count -= 1 if count == 0: major = val count = 1 return major

时间复杂度$O(n)$，空间复杂度$O(1)$

第三种：排序

class Solution: def majorityElement(self, nums: List[int]) -> int: nums = sorted(nums) return nums[len(nums) // 2]

时间复杂度$O(nlogn)$，空间复杂度$O(logn)$

题解区补充解答

第一种：随机化

import random class Solution: def majorityElement(self, nums): majority_count = len(nums)//2 while True: candidate = random.choice(nums) if sum(1 for elem in nums if elem == candidate) > majority_count: return candidate

第二种：分治

class Solution: def majorityElement(self, nums, lo=0, hi=None): def majority_element_rec(lo, hi): # base case; the only element in an array of size 1 is the majority # element. if lo == hi: return nums[lo] # recurse on left and right halves of this slice. mid = (hi-lo)//2 + lo left = majority_element_rec(lo, mid) right = majority_element_rec(mid+1, hi) # if the two halves agree on the majority element, return it. if left == right: return left # otherwise, count each element and return the "winner". left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left) right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right) return left if left_count > right_count else right return majority_element_rec(0, len(nums)-1)

以上两种解答的具体思路参考：官方解答。

第三种：位运算

class Solution { public: int majorityElement(vector<int>& nums) { int res=0; for(int i=0;i<32;i++) { int ones=0; for(int n:nums) ones += (n >> i) & 1; //位运算法统计每个位置上1出现的次数，每次出现则ones+1 res += (ones > nums.size()/2) << i; //如果1出现次数大于2分之1数组的长度，1即为这个位置的目标数字 } return res; } };

参考：c++ 5种方法 排序，哈希，投票，随机数，位运算-z