【Python3】【力扣题】169. 多数元素

元素"/>

【Python3】【力扣题】169. 多数元素

【力扣题】题目描述：

众数：一组数据中出现次数最多的数据。

【Python3】代码：

1、解题思路：哈希表。使用哈希映射存储各元素以及出现的次数，哈希映射中的键值对中的键为元素、值为该元素出现次数。

知识点：collections.Counter(...)：Counter对象实例化。用字典形式为各元素计数。

（1-1）遍历哈希映射中的键值对，返回键值对中的值的元素。

知识点：字典形式.items()：返回可遍历的键值对（元组形式即(键,值)）。

class Solution:def majorityElement(self, nums: List[int]) -> int:from collections import Counteradict = Counter(nums)m = len(nums) // 2for key,val in adict.items():if val > m:return key

（1-2）对于哈希映射中的键值对，获取值最大的那个键。

知识点：字典形式.items()：返回可遍历的所有键。

              字典形式.get(...)：通过键获取对应的值。

              max(...)：获取最大值。

class Solution:def majorityElement(self, nums: List[int]) -> int:from collections import Counteradict = Counter(nums)return max(adict.keys(),key=adict.get)

2、解题思路：排序。从小到大依次排序，出现次数，那么中间那个数一定是众数。

知识点：序列.sort()：在原序列上按从小到大排序。

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

3、解题思路：随机抽数。出现次数，随机抽取一个数大概率就是众数。

知识点：random.choice(...)：一组数据中随机选取一个。

              len(序列)：获取序列的长度。

              sum(...)：求和。

class Solution:def majorityElement(self, nums: List[int]) -> int:import randomm = len(nums) // 2while True:rand = random.choice(nums)if sum(1 for x in nums if x == rand) > m:return rand

4、解题思路：分治算法。将一组数据递归分成左右2部分，直到子区间长度为1，再回溯合并比较左右区间值以及值的数量。最终返回数量多的那个值。

知识点：闭包（A函数里有B函数。A函数返回值为B函数但不加括号，实际调用时才加括号），递归（B函数里调用B函数自身）。

class Solution:def majorityElement(self, nums: List[int]) -> int:def recurse(low,high) -> int:# 最终分成只有一个数的数组，并返回值if low == high: return nums[low]# 从中间分成左右2部分（递归）mid = (high-low) // 2 + lowleft = recurse(low,mid)right = recurse(mid+1,high)# 分完后，回溯比较左右2部分值以及值的数量。# 若左右2部分的值相同，返回哪个都一样if left == right: return left# 若左右2部分的值不同，左右2部分合并比较2个值的数量，返回数量多的那个值left_count = sum(1 for i in range(low,high+1) if nums[i] == left)right_count = sum(1 for i in range(low,high+1) if nums[i] == right)return left if left_count > right_count else rightreturn recurse(0,len(nums)-1)

5、解题思路：Boyer-Moore投票算法。依次遍历每个元素，既然出现次数，众数即使和其他数抵消，最终剩余的一定是众数。

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