本文章出自【码同学软件测试】

算法面试—找众数

前提:

现在测试工程师的面试,或多或少都会问到编程技术.在编程技术中,往往会挑选一个简单的算法题.很多同学一看到这,往往就不知如何是好了.后果轻则被压低薪水,重则失去这次面试机会.

码同学公众号：自动化软件测试

码同学抖音号：小码哥聊软件测试

 其实面试中的算法,可以通过刷题来进行准备.下面分享下最近面试遇到的算法面试题

 

 题目-寻找一个列表中的众数

给定一个大小为n的数组,找到其中的众数

*众数:是指在数组中出现次数大于"n/2"的元素

示例:

给定数组:list = [1,2,5,5,5,5,7]

预期输出: 5

LV1:直接解题

先用最直接的方式,尝试转化题目

deffunc(num:list):  #定义一个函数,接收"列表"数据

    res = []         #定义一个变量接收结果 

对于大于"n/2"这条需求,可以先求出n

n = len(num)           #用len函数得到n

找到数组里的众数,可以理解为:在数组中进行循环比较.

条件是 当前元素出现次数(list.count()函数可以得出)大于 n/2

如果符合条件,则存到res变量中

对于大于"n/2"这条需求,可以先求出n

fori innum:   #遍历num

    now_time = num.count(i)     #得到当前遍历项的出现次数

    if now_time > n/2:             #如果该数字出现次数大于n/2

  res.append(i)   #则加入结果

由于循环中,会把每一个众数都加到结果中得到如下结果

[5, 5, 5, 5]

所以在加一部去重复数据

returnset(res)

结果:

免费领取 码同学软件测试 课程笔记+超多学习资料+完整视频+最新面试题，可以转发文章 + 私信「码同学666」获取资料哦

Lv2:简化

上述方案中,力求快速实现需求.在细节上比较冗余,这里在进行一步简化.

deffunc(num:list):#定义一个函数,接收"列表"数据

# res = []           #实际上由于众数的规则(数量>一般),一个数组中只可能有一个.所以遇到直接返回就好了

# n = len(num)       #把这步计算直接放到if条件中

foriinnum:#遍历num

# now_time = num.count(i)       #可以将这个计算直接放到条件上

ifnum.count(i)>len(num)/2:#可以将n/2的计算,直接放到这

returni#则加入结果

效果如下:

LV3效率优化

从功能的角度来说,上述方案是可行的.但是一旦遇到海量数据,重复计算list.count()非常耗时.如图:

这个测试数据中有5w+个元素,计算非常巨大

重新思考题目中的众数,发现几个特性:

①一个数组中最多只有1个众数(不会出现2个过半数的元素)

②如果数组是从大到小排列(list.sort()函数可以进行排序),那么中间的那个数字一定是众数

③对于数组而言,也分奇数/偶数元素

如果是奇数

# 数组的元素数量是奇数

l = [1,1,3,3,3]

print(len(l) // 2)可以使用"整除"得到中点

# 这时恰好取到数组的中点,那么取到的一定是众数

如果是偶数

# 数组的元素数是偶数

 l = [1,1,3,3,3,3]

 print(len(l) // 2)

# 取到的是绝对中点向后取整，此案例使4/7

# 此时的众数也一定是>7/2,即至少出现4次

# 所以l[len(2//l)]一定是众数

重写:

# 数组的元素数是偶数

def majorityElement(nums):

    nums.sort()

    returnnums[len(nums)// 2]

效果如图:

结论:速度比起直接解法,快了20倍以上

END

免费领取码同学软件测试课程笔记+超多学习资料+学习完整视频，可以关注我们公众号哦：自动化软件测试

本文著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。