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

本文主要是介绍数组中出现次数超过一半的数字（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

第一思路：

给这个数组排好序，然后统计数组中每个数字在数组中出现的次数，然后看出现次数最多的这个元素的个数有没有大于数组长度的一半，有，则返回，没有返回0。

优化思路：基于partition( )方法的O（n）算法

数组中有一个数字出现的次数超过了数组长度的一般，如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。即，这个数字就是统计学上的中位数，即长度为n的数组中第n/2大的数字。

受快速排序的启发，在随机快速排序算法中，先在数组中随机选择一个数字，然后调整数组中数字的顺序，使得比选中的数字小的数字都排在它的左边，比选中大的数字都排在它的右边。如果选中的数字下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们接着在它的右边部分的数组中查找。这是一个典型的递归。

代码实现：