当前位置:网站首页>测试员的算法面试题-找众数
测试员的算法面试题-找众数
2022-07-04 19:22:00 【码同学软件测试】
算法面试—找众数
前提:
现在测试工程师的面试,或多或少都会问到编程技术.在编程技术中,往往会挑选一个简单的算法题.很多同学一看到这,往往就不知如何是好了.后果轻则被压低薪水,重则失去这次面试机会.
其实面试中的算法,可以通过刷题来进行准备.下面分享下最近面试遇到的算法面试题
题目-寻找一个列表中的众数
给定一个大小为n的数组,找到其中的众数
*众数:是指在数组中出现次数大于"n/2"的元素
示例:
给定数组:list = [1,2,5,5,5,5,7]
预期输出: 5
LV1:直接解题
先用最直接的方式,尝试转化题目
def func(num:list): #定义一个函数,接收"列表"数据
res = [] #定义一个变量接收结果
对于大于"n/2"这条需求,可以先求出n
n = len(num) #用len函数得到n
找到数组里的众数,可以理解为:在数组中进行循环比较.
条件是 当前元素出现次数(list.count()函数可以得出)大于 n/2
如果符合条件,则存到res变量中
对于大于"n/2"这条需求,可以先求出n
for i in num: #遍历num
now_time = num.count(i) #得到当前遍历项的出现次数
if now_time > n/2: #如果该数字出现次数大于n/2
res.append(i) #则加入结果
由于循环中,会把每一个众数都加到结果中得到如下结果
[5, 5, 5, 5]
所以在加一部去重复数据
return set(res)
结果:
Lv2:简化
上述方案中,力求快速实现需求.在细节上比较冗余,这里在进行一步简化.
def func(num:list): #定义一个函数,接收"列表"数据
# res = [] #实际上由于众数的规则(数量>一般),一个数组中只可能有一个.所以遇到直接返回就好了
# n = len(num) #把这步计算直接放到if条件中
for i in num: #遍历num
# now_time = num.count(i) #可以将这个计算直接放到条件上
if num.count(i) > len(num)/2: #可以将n/2的计算,直接放到这
return i #则加入结果
效果如下:
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()
return nums[len(nums) // 2]
效果如图:
结论:速度比起直接解法,快了20倍以上
边栏推荐
- 九齐单片机NY8B062D单按键控制4种LED状态
- 语义化标签的优势和块级行内元素
- 企业数字化转型最佳实践案例:基于云的数字化平台系统安全措施简介与参考
- 栈:如何实现有效括号的判断?
- Automatic insertion of captions in word
- E-week finance | Q1 the number of active people in the insurance industry was 86.8867 million, and the licenses of 19 Payment institutions were cancelled
- How does the computer save web pages to the desktop for use
- Lingyun going to sea | Murong Technology & Huawei cloud: creating a model of financial SaaS solutions in Africa
- 易周金融 | Q1保险行业活跃人数8688.67万人 19家支付机构牌照被注销
- Understand the reading, writing and creation of files in go language
猜你喜欢
Win11共享文件打不开怎么办?Win11共享文件打不开的解决方法
二叉树的四种遍历方式以及中序后序、前序中序、前序后序、层序创建二叉树【专为力扣刷题而打造】
idea恢复默认快捷键
See how Tencent does interface automation testing
关于联邦学习和激励的相关概念(1)
Flet教程之 05 OutlinedButton基础入门(教程含源码)
Selected review | machine learning technology for Cataract Classification / classification
#夏日挑战赛#带你玩转HarmonyOS多端钢琴演奏
阿里测试师用UI自动化测试实现元素定位
Idea restore default shortcut key
随机推荐
Qt编写物联网管理平台38-多种数据库支持
Idea restore default shortcut key
针对深度学习的“失忆症”,科学家提出基于相似性加权交错学习,登上PNAS
Flet tutorial 04 basic introduction to filledtonalbutton (tutorial includes source code)
Lingyun going to sea | Wenhua online & Huawei cloud: creating a new solution for smart teaching in Africa
二叉树的四种遍历方式以及中序后序、前序中序、前序后序、层序创建二叉树【专为力扣刷题而打造】
【ISMB2022教程】图表示学习的精准医疗,哈佛大学Marinka Zitnik主讲,附87页ppt
What if the WiFi of win11 system always drops? Solution of WiFi total drop in win11 system
BFC面试简述
word中插入圖片後,圖片上方有一空行,且删除後布局變亂
企业数字化转型最佳实践案例:基于云的数字化平台系统安全措施简介与参考
接口设计时的一些建议
How to adapt your games to different sizes of mobile screen
Ziguang zhanrui completed the first 5g R17 IOT NTN satellite on the Internet of things in the world
最长的可整合子数组的长度
面对同样复杂的测试任务为什么大老很快能梳理解决方案,阿里十年测试工程师道出其中的技巧
奏响青春的乐章
go语言笔记(2)go一些简单运用
强化学习-学习笔记2 | 价值学习
tcp为啥是三次握手和四次挥手