剑指Offer(Python多种思路实现):数组中出现次数超过一半的数字

面试39题： 题目：数组中出现次数超过一半的数字 题：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 解题思路一：根据数组特点找出时间复杂度为O(n)的算法。因为该数字出现次数比其他所有数字出现的次数之和还要多，所有要找的数字肯定是最后一次把次数设为1时对应的数字。 class Solution: def MoreThanHalfNum_Solution(self, numbers): # write co 在编程面试中，"数组中出现次数超过一半的数字" 是一个常见的问题，它考察了对数据结构和算法的理解。本题目的目标是找到数组中出现次数超过数组长度一半的元素，如果没有这样的元素，则返回0。以下是几种不同的Python实现方法。 ### 解题思路一：摩尔投票法（Majority Voting Algorithm） 这种方法基于一个观察：如果有这样一个多数元素，每次从数组中选择两个不同的元素并消除它们，最后剩下的那个元素就是多数元素。在Python中，我们可以用以下方式实现： ```python class Solution: def MoreThanHalfNum_Solution(self, numbers): if not numbers or len(numbers) <= 0: return 0 res = numbers[0] times = 1 for i in range(1, len(numbers)): if times == 0: res = numbers[i] times = 1 elif numbers[i] == res: times += 1 else: times -= 1 # 检查其次数是否大于数组的一半 return self.CheckMoreThanHalf(numbers, res) def CheckMoreThanHalf(self, numbers, number): length = len(numbers) times = 0 for i in range(length): if numbers[i] == number: times += 1 return times * 2 > length ``` 在这个实现中，`MoreThanHalfNum_Solution` 方法首先初始化结果变量 `res` 和计数器 `times`，然后遍历数组。当遇到不同元素时，`times` 减1，直到 `times` 为0，此时更新 `res` 为当前元素。如果之后再遇到相同的元素，`times` 加1。通过 `CheckMoreThanHalf` 方法确认多数元素是否真的超过了数组长度的一半。 ### 解题思路二：哈希表（Hash Table） 利用哈希表可以更高效地统计每个元素的出现次数，但这种方法需要额外的空间。Python中的实现如下： ```python class Solution: def MoreThanHalfNum_Solution(self, numbers): if not numbers or len(numbers) <= 0: return 0 count = {} for num in numbers: if num in count: count[num] += 1 else: count[num] = 1 for num, freq in count.items(): if freq * 2 > len(numbers): return num return 0 ``` 在这里，我们创建一个字典 `count` 来存储每个元素及其出现的次数。遍历数组后，检查字典中的每个元素，如果其出现次数大于数组长度的一半，就返回该元素。 ### 解题思路三：中位数法 这种方法假设数组已经排序，可以通过找到中位数来解决。如果中位数是多数元素，那么在数组的前半部分找不到相同的元素，而在后半部分会找到至少一个相同的元素。因此，多数元素应该出现在中位数的位置。但是，这个方法只适用于已排序的数组，且在未排序的数组中应用排序操作会导致时间复杂度增加到O(n log n)。Python代码如下： ```python def majority_element(nums): return sorted(nums)[len(nums) // 2] ``` 然而，这个方法不能直接用于原题，因为它假设了数组已排序，而题目没有这样的要求。因此，在实际应用中，不建议使用此方法。 总结来说，处理这个问题的关键在于理解多数元素的性质，并选择合适的数据结构和算法来优化时间复杂度。摩尔投票法提供了线性时间复杂度的解决方案，而哈希表则提供了一种空间效率较高的方法。在实际面试中，应根据具体场景和要求来选择合适的策略。