image.png
hash表
1. 思路很简单，先遍历数组，存储每个元素的个数 2. 遍历hash表，拿到大于 n/2的数字，直接return
class Solution: def majorityElement(self, nums: List[int]) -> int: hash = dict() for n in nums: if n not in hash: hash[n] = 1 else: hash[n] += 1 for k, v in hash.items(): if v > len(nums) / 2: return k return -1
时间复杂度: O(N)
空间复杂度: O(N)
投票算法
思路很简单，假设你是秦始皇，数组里面有很多其他国家，你们秦兵遇到自己人就+1，遇到其他人就-1，如果你超过了所有国家一半的兵力，那么最后活下来的肯定就是你的士兵。这里之所以能这么确定，是因为题目强调了一定存在多数元素！ 代码思路是，开始遍历数组，如果当前的士兵数量是0，则把当前士兵设置为遍历到的元素，比如: 秦 接下来如果遇到秦，则count+1, 遇到的是赵或者其他士兵，则秦和赵士兵同归于尽。下一轮遍历，由于秦的count是0了，则将当前士兵设置为遍历到的士兵。
class Solution: def majorityElement(self, nums: List[int]) -> int: if len(nums) == 0: return -1 # 当前士兵数量 count = 0 # 当前士兵 current = None for n in nums: if count == 0: current = n count += 1 if n == current else -1 return current
时间复杂度: O(N)
空间复杂度: O(1)
