题目描述给定一个大小为n的数组nums返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例输入nums [3, 2, 3] 输出3 输入nums [3, 3, 4] 输出3提示n nums.length1 n 5 * 10^4-10^9 nums[i] 10^9思路一排序取中位数由于多数元素出现的次数严格大于n/2所以把数组排序之后位于中间位置的元素一定是多数元素。这是最直观、代码最短的写法。class Solution: def majorityElement(self, nums: list[int]) - int: nums.sort() return nums[len(nums) // 2]复杂度分析时间复杂度O(n log n)主要开销在排序。空间复杂度O(log n)排序所需的栈空间原地排序。思路二哈希表计数遍历数组用字典记录每个元素出现的次数最后取出出现次数最多的那个元素。思路清晰适合作为通用解法。class Solution: def majorityElement(self, nums: list[int]) - int: count {} for num in nums: if num in count: count[num] 1 else: count[num] 1 return max(count, keycount.get)复杂度分析时间复杂度O(n)只需遍历一次数组。空间复杂度O(n)最坏情况下需要存储所有不同的元素。小提示变量名不要用dict它会覆盖 Python 内置的dict类型建议改成count或freq。思路三摩尔投票法最优解摩尔投票法的核心思想是“抵消”把多数元素记为1其他元素记为-1全部加起来一定大于 0。因此可以维护一个候选元素candidate和计数器count当count 0时说明之前的元素都被抵消完了把当前元素设为新的候选当前元素等于候选时count 1当前元素不等于候选时count - 1。遍历结束后剩下的候选元素就是多数元素。class Solution: def majorityElement(self, nums: list[int]) - int: # 摩尔投票 count 0 candidate None for num in nums: if count 0: candidate num count 1 elif num candidate: count 1 else: count - 1 return candidate复杂度分析时间复杂度O(n)只需遍历一次数组。空间复杂度O(1)只用了常数个变量。完整测试代码if __name__ __main__: print(Solution().majorityElement([3, 3, 4])) # 输出 3 print(Solution().majorityElement([3, 2, 3])) # 输出 3 print(Solution().majorityElement([1])) # 输出 1三种解法对比解法时间复杂度空间复杂度特点排序取中位数O(n log n)O(log n)代码最短依赖排序哈希表计数O(n)O(n)通用性强易理解摩尔投票法O(n)O(1)最优解面试常考总结本题的关键在于理解“多数元素出现次数大于n/2”这一条件带来的性质排序后中位数必为答案而摩尔投票法则利用元素之间的相互抵消在O(n)时间、O(1)空间内得到结果。实际面试中建议先说出哈希表思路再给出摩尔投票法作为优化体现对复杂度优化的思考过程。