01 算法面试—找众数

现在测试工程师的面试，或多或少都会问到编程技术。在编程技术中，往往会挑选一个简单的算法题。很多同学一看到这，往往就不知如何是好了。后果轻则被压低薪水，重则失去这次面试机会，其实面试中的算法，可以通过刷题来进行准备，下面分享下最近面试遇到的算法面试题

02 寻找一个列表中的众数

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

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

示例:

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

预期输出：5

LV1：直接解题

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

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

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

• 1

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

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

• 1

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

条件是 当前元素出现次数(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)                #则加入结果

• 1
• 2
• 3
• 4

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

[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    #则加入结果

• 1
• 2
• 3
• 4
• 5
• 6
• 7

效果如下:

LV3：效率优化

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

如图:

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

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

• 一个数组中最多只有1个众数(不会出现2个过半数的元素)
• 如果数组是从大到小排列(list.sort()函数可以进行排序),那么中间的那个数字一定是众数
• 对于数组而言,也分奇数/偶数元素

如果是奇数

# 数组的元素数量是奇数

l = [1,1,3,3,3]
print(len(l) // 2)可以使用"整除"得到中点
# 这时恰好取到数组的中点,那么取到的一定是众数

• 1
• 2
• 3
• 4
• 5

如果是偶数

# 数组的元素数是偶数

 l = [1,1,3,3,3,3]
 print(len(l) // 2)
# 取到的是绝对中点向后取整，此案例使4/7
# 此时的众数也一定是>7/2,即至少出现4次
# 所以l[len(2//l)]一定是众数

• 1
• 2
• 3
• 4
• 5
• 6
• 7

重写:

# 数组的元素数是偶数
def majorityElement(nums):
    nums.sort()
    return nums[len(nums) // 2]

• 1
• 2
• 3
• 4

效果如图:

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

感谢每一个认真阅读我文章的人！！！

作为一位过来人也是希望大家少走一些弯路，如果你不想再体验一次学习时找不到资料，没人解答问题，坚持几天便放弃的感受的话，在这里我给大家分享一些自动化测试的学习资源，希望能给你前进的路上带来帮助。

软件测试面试文档

我们学习必然是为了找到高薪的工作，下面这些面试题是来自阿里、腾讯、字节等一线互联网大厂最新的面试资料，并且有字节大佬给出了权威的解答，刷完这一套面试资料相信大家都能找到满意的工作。 

          视频文档获取方式：
这份文档和视频资料，对于想从事【软件测试】的朋友来说应该是最全面最完整的备战仓库，这个仓库也陪伴我走过了最艰难的路程，希望也能帮助到你！以上均可以分享，点下方小卡片即可自行领取。