面试题：已知数组中有一个数字出现的次数，超过数组长度的一半，要求找出这个数字。

概述已知数组中有一个数字出现的次数，超过数组长度的一半，要求找出这个数字。题目来源：笔试面试题目：阿里选班长三种方法python实现：1、排序：由于目标元素的次数超过数组长度的一半，所以排序后直接取中间元素就行。pythonsorted函数采用的是Timsort排序，最坏时间复杂度为：O(nlogn)，空 已知数组中有一个数字出现的次数，超过数组长度的一半，要求找出这个数字。

题目来源：笔试面试题目：阿里选班长

三种方法python实现：

1、排序：

由于目标元素的次数超过数组长度的一半，所以排序后直接取中间元素就行。
python sorted函数采用的是Timsort排序，最坏时间复杂度为：O(nlogn)，空间复杂度为：O(n)

python代码：

l = [6,2,5,4,2,2,2,2,5]n = len(l)print(sorted(l)[int(n/2)])

2、计数统计

将出现次数多于一半的元素取出来

python代码：

l = [6,2,5,4,2,2,2,2,5]for i in set(l):    if l.count(i)>len(l)/2:        print(i)

3、摩尔投票

摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

例如：玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，而且不能内斗，每个人口出去干仗都恰好能一对一同归于尽，最后还有人活下来的国家就是胜利。
最差的情况是所有人都联合起来对付你，你人数多于一半，最后肯定是你赢，或者其他国家也会相互攻击，最后肯定还是你赢。

python代码：

l = [6,2,5,4,2,2,2,2,5]array = []for i in l:    if len(array)>0:        if array[0]==i:            array.append(i)        else:            array.pop()      else:        array.append(i)print(array[0])   

总结

以上是内存溢出为你收集整理的面试题：已知数组中有一个数字出现的次数，超过数组长度的一半，要求找出这个数字。全部内容，希望文章能够帮你解决面试题：已知数组中有一个数字出现的次数，超过数组长度的一半，要求找出这个数字。所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。