剑指offer

数组中出现次数超过一半的数字( python实现 ）

一、题目描述

题目：数组中出现次数超过一半的数字 数组中有一个数字的次数超过数组长度的一半，请找出这个数字。例如，输入一个长度为 9 的数组 {1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2。

二、解题思路

  暂略。（此处主要作为书中python实现补充）

三、代码实现

  从题目可知，数组中肯定是存在次数超过长度一半的数字，因此，可采用以下代码实现的方式。

def MoreThanHalfNum(arr): if len(arr) == 0: return result = arr[0] times = 1 for i in range(1,len(arr)): if times == 0: result = arr[i] times = 1 elif result == arr[i]: times = times+1 else: times = times-1 return result

  简单举例测试如下：

>>> arr = [1, 2, 3, 2, 2, 2, 5, 4, 2] >>> MoreThanHalfNum(arr) Out: 2

  补充 ：若是要处理的数组中，有可能不存在超过一半的数字，以上代码返回的结果就有问题了。可考虑 Python 的字典，记录下每个数字 ( key ) 及其出现次数 ( value )，然后扫描字典，返回 value 值大于长度一半所对应的 key，若是没有，则返回 None。时间复杂度还是为 $O(n)$，会增加一定的空间复杂度。