JavaScript 数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

题目：

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

思路：

（1）对数组进行排序，排序后的中位数就是所求数字。这种方法的时间复杂度取决于我们采用的排序方法的时间复杂度，因此最快为 O(nlogn)。

（2）由于所求数字的数量超过了数组长度的一半，因此排序后的中位数就是所求数字。因此我们可以将问题简化为求一个数组的中 位数问题。其实数组并不需要全排序，只需要部分排序。我们通过利用快排中的 partition 函数来实现，我们现在数组中随 机选取一个数字，而后通过 partition 函数返回该数字在数组中的索引 index，如果 index 刚好等于 n/2，则这个数字 便是数组的中位数，也即是要求的数，如果 index 大于 n/2，则中位数肯定在 index的左边，在左边继续寻找即可，反之 在右边寻找。这样可以只在 index 的一边寻找，而不用两边都排序，减少了一半排序时间，这种方法的时间复杂度为 O(n)。

（3）由于该数字的出现次数比所有其他数字出现次数的和还要多，因此可以考虑在遍历数组时保存两个值：一个是数组中的一个数 字，一个是次数。当遍历到下一个数字时，如果下一个数字与之前保存的数字相同，则次数加1，如果不同，则次数减1，如果 次数为0，则需要保存下一个数字，并把次数设定为1。由于我们要找的数字出现的次数比其他所有数字的出现次数之和还要大， 则要找的数字肯定是最后一次把次数设为1时对应的数字。该方法的时间复杂度为O(n)，空间复杂度为 O(1)。

详细资料可以参考： 《出现次数超过一半的数字》

更多面试题

如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。

这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！