免费建立个人视频网站,企业网站建设需要做些什么,小网站 收入,wordpress环境虚拟机安装对于给定的一个长度为n的数组nums#xff0c;需要找出起重工出现次数大于n/2向下取整的元素#xff0c;假设给定的数组中一定存在符合给定要求的数#xff0c;例如给定如下的例子#xff1a; 添加图片注释#xff0c;不超过 140 字#xff08;可选#xff09; 添加图片注…对于给定的一个长度为n的数组nums需要找出起重工出现次数大于n/2向下取整的元素假设给定的数组中一定存在符合给定要求的数例如给定如下的例子 添加图片注释不超过 140 字可选 添加图片注释不超过 140 字可选
对于这个问题可以使用分治算法来将问题规模不断缩小在执行过程中减少部分计算这样就可以提高执行效率。
对于分治算法解决思路如果想要在n个数中寻找出现次数最多的数字将问题规模缩小可以先找出前n/2部分出现次数最多的数head再找出后n/2部分出现次数最多的数tail如果这两者相等则说明出现次数最多的数字已经找到了而如果两者不相等则需要再在n个数字中搜索head和tail分别出现的次数选择出现次数最大的那个作为最终的结果。
要对于找出前n/2部分出现次数最多的数的过程与上述的过程是一致的也就是对n/2部分的前半部分和后半部分分别作判断依次进行递推直至判断部分的长度为1位置这样就可以将该数进行返回了。
对于第一个例子的整个分治过程如下 添加图片注释不超过 140 字可选
根据每次分治返回的head和tail进行判断最终返回的是1为出现次数最多的数字。
使用python实现的代码如下
class Solution:def findnum(self, nums):def func(low,high):if lowhigh:return nums[low]midlow(high-low)//2headfunc(low,mid)tailfunc(mid1,high)if headtail:return tailhead_countsum(1 for i in range(low,high1) if nums[i]head)tail_countsum(1 for i in range(low,high1) if nums[i]tail)return head if head_counttail_count else tailreturn func(0,len(nums)-1)
对于该问题可以提供其他的一些解决方式例如可以使用字典的方式来结局将nums中的每个数字作为键key然后将每个数字出现的次数作为值value然后将nums转换成一个字典dic这样就可以使用max(dic.keys(),keydic.get)这个方法来获取字典dic中value的最大值所对应的键key了。对于max(dic.keys(),key)这个方法首先是会遍历字典然后将返回值作为参数传递给key所对应的函数再将函数的执行结果传回给key以此时key的值来作为标准进行判断大小返回一个最大值即可python实现的代码如下
class Solution:def findnum(self, nums):dic{}for i in nums:dic[i]dic.get(i,0)1return max(dic.keys(),keydic.get)
