面试题:数组中出现次数超过一半的数字题目：数组中

18 查阅

面试题:数组中出现次数超过一半的数字题目：数组中有一个数字出现的次数过超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组｛1，2，3，2，2，2，5，4，2｝。由于数字2在数组中出现了5次

参考答案:

正确答案：

看到这道题很多应聘者就会想要是这个数组是排序的数组就好了。如果是排好序的数组，那么我们就能很容易统计出每个数字出现的次数。题目给出的数组没有说是排序的，因此我们需要先给它排序。排序的时间复杂度是O(n/ogn)。最直观的算法通常不是面试官满意的算法，接下来我们试着找出更快的算法。
◆解法一：基于Partition函数的O(n)算法
如果我们回到题目本身仔细分析，就会发现前面的思路并没有考虑到数组的特性：数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，

数组