LeetCode热题100-多数元素

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

读题后其实很容易想到使用哈希方法去找多数元素，时间复杂度On，空间复杂度On.

class Solution: def majorityElement(self, nums: List[int]) -> int: if not nums: return -1 res = {} for num in nums: if num in res: res[num] += 1 continue res[num] = 1 max_num, max_count = 0, -1 for key, value in res.items(): if value > max_count: max_num = key max_count = value return max_num

方法二：摩尔投票法，相同票加 1，不同票减 1，本质就是选票的 “对抗与抵消”。这样多数元素（超过半数）一定能在抵消后剩下来，就像选举中得票过半者最终胜出。时间复杂度On，空间复杂度O1

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

方法三：排序：时间复杂度Onlogn

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