练习：找出出现次数最多的数字

题： 给定一个长度为 n 的数组 nums，请找出其中出现次数大于 n/2 向下取整的元素。
'''
如：
nums = [1,2,1,2,1]
出现最多的元素是1
长度为5，5/2 向下取整是2, 1出现的次数大于2
'''
### 分治算法

 1 class Solution(object):
 2     def findnum(self,nums):
 3         def func(low,high):
 4             # 当二者相等的时候，说明长度为1，可以直接返回当前元素
 5             if low==high:
 6                 return nums[low]
 7             # 找到中位
 8             mid=low+(high-low)//2
 9             # 前半部分和后半部分
10             head=func(low,mid)
11             tail=func(mid+1,high)
12             # 如果相等，说明已经找到
13             if head==tail:
14                 return tail
15             # 统计出现的次数
16             head_count=sum(1 for i in range(low,high+1) if nums[i]==head)
17             tail_count = sum(1 for i in range(low, high+1) if nums[i]==tail)
18             return head if head_count>tail_count else tail
19         return func(0,len(nums)-1)
20 
21 # eg.
22 nums=[1,4,2,3,4,4,4]
23 demo=Solution()
24 acount=demo.findnum(nums)
25 print(acount) # 4

### 字典法

 1 class Solution_Dic(object):
 2     def findnum(self,nums):
 3         dic={}
 4         # 将 nums 中每个数字作为key，将每个数字出现的次数作为value，将nums 转换成一个字典dic
 5         for i in nums:
 6             dic[i]=dic.get(i,0)+1
 7         # 获取字典dic 中value 的最大值所对应的键
 8         return max(dic.keys(),key=dic.get)
 9 
10 # eg.
11 nums=[1,4,2,3,4,4,4]
12 demo2=Solution_Dic()
13 acount_dic=demo2.findnum(nums)
14 print(acount_dic) # 4

### 空间优化解法
'''
# 出现的次数大于其他数字，当遍历到某一个数字时，如果等于re ,则次数加1；如果不等于re ，则次数减1；
# 当次数已经为0 时，则将下一个数字赋值给re ，并且times 更新为1；
# 最终留下来的re 就是出现次数最多的数字。
'''

 1 class SolutionK(object):
 2     def findnums(self,nums):
 3         times=1
 4         re=nums[0]
 5         for i in range(1,len(nums)):
 6             if times==0:
 7                 re=nums[i]
 8                 times+=1
 9             elif nums[i]==re:
10                 times+=1
11             else:
12                 times-=1
13         return re

2023-9-10笔记