Python解决“找出整形数组中占比超过一半的数”问题

这里写目录标题 问题描述测试样例解决思路代码法1法2

问题描述

小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。

测试样例

样例1： 输入：array = [1, 3, 8, 2, 3, 1, 3, 3, 3] 输出：3

样例2： 输入：array = [5, 5, 5, 1, 2, 5, 5] 输出：5

样例3： 输入：array = [9, 9, 9, 9, 8, 9, 8, 8] 输出：9

解决思路

这道题目综合运用了哈希表和计数算法知识。题目要求找出数组中出现次数超过一半的数字。由于题目明确指出存在这样的数字，因此我们可以通过统计每个数字的出现次数来找到答案。使用哈希表（Python中的Counter）可以高效地统计每个数字的出现次数，然后遍历哈希表找到出现次数超过数组长度一半的数字。

统计数字出现次数：使用Counter对数组中的每个数字进行计数，生成一个哈希表，键为数字，值为该数字在数组中出现的次数。 查找超过一半的数字：遍历哈希表，找到第一个满足出现次数乘以2大于数组长度的数字，即为答案。

时间复杂度：O(n)，其中n是数组的长度。我们需要遍历数组一次来统计数字的出现次数，然后再遍历哈希表一次来找到目标数字。 空间复杂度：O(n)，哈希表的空间复杂度与数组中不同数字的数量成正比，最坏情况下为n。

代码 法1

根据思路逻辑解法

def solution(array): # 创建一个字典来记录每个数字的出现次数 count_dict = {} # 遍历数组，统计每个数字的出现次数 for num in array: # 如果数字已经在字典中，增加其计数 if num in count_dict: count_dict[num] += 1 else: # 如果数字不在字典中，初始化其计数为1 count_dict[num] = 1 # 找到出现次数超过数组长度一半的数字 half_length = len(array) // 2 for num, count in count_dict.items(): if count > half_length: return num # 如果没有找到符合条件的数字，返回0（虽然题目保证一定存在这样的数字） return 0 if __name__ == "__main__": # 添加你的测试用例 print(solution(array = [1, 3, 8, 2, 3, 1, 3, 3, 3])) print(solution(array = [5, 5, 5, 1, 2, 5, 5])) print(solution(array = [9, 9, 9, 9, 8, 9, 8, 8])) 法2

简化方法：

def solution(array: list) -> int: from collections import Counter c = Counter(array) return next(k for k, v in c.items() if v * v > len(array)) if __name__ == '__main__': print(solution(array = [1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3) print(solution(array = [5, 5, 5, 1, 2, 5, 5]) == 5) print(solution(array = [9, 9, 9, 9, 8, 9, 8, 8]) == 9)