考点：时间效率、数组
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
代码格式
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
}
}
解题一-先排序再找中位数（利用Arrays工具类和IntStream流求解）
所用到的知识点：
Arrays.sort(array);可以对数组进行排序；
Stream实例.filter(过滤规则)可对流中的数据进行筛选；
1.思路
（1）排序，取中间的数字设为i,
（2）用i过滤数组，如果为i的个数超过半数，则i为所求，否则结果为0；
2.代码
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
//Arrays.sort(array)对数组进行排序
Arrays.sort(array);
//取数组中间的数字设为i
int i=array[array.length/2];
//用i过滤数组，三元运算进行判断
return IntStream.of(array).filter(k->k==i).count()>array.length/2?i:0;
}
}
上述代码理解：
IntStream.of(array)，表示写入array中的具体值，如 Stream s4 = Stream.of("1", "2", "3","4")；
IntStream表示元素只有int类型的流；
filter(k->k==i) 其中k定义为数组中的变量元素，k->k==i表示过滤的范围为k到i，count总计元素的个数。
解题二-先排序再找中位数（利用Arrays工具类和for循环）
1.思路
数组中有一个数字出现的次数超过了数组长度的一半。如果把这个数组排序，那么排序之后位于数组中间的数字一定就是那个出现次数超过数组长度一半的数字。
在随机快速排序算法中，我们先在数组中随机选择一个数字，然后调整数组中数字的顺序， 使得比选中的数字小数字都排在它的左边，比选中的数字大的数字都排在它的右边。如果这个选中的数字的下标刚好是n/2，那么这个数字就是数组的中位数。如果它的下标大于n/2 ，那么中位数应该位于它的左边，我们可以接着在它的左边部分的数组中查找。如果它的下标小于n/2，那么中位数应该位于它的右边，我们可以接着在它的右边部分的数组中查找。这是一个典型的递归过程。
先将数组排序，取出下标为长度一半的数字，将其遍历并进行计数，如果计数的结果大于数组长度的一半，就返回该值，否则返回0
2.代码
import java.util.Arrays;
import java.util.stream.IntStream;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Arrays.sort(array);
int half = array.length / 2;
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == array[half])
count++;
}
if (count > half)
return array[half];
else
return 0;
}
}
解题三-直接遍历数组
1.思路
数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。
（1）在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次数。
（2）当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。
（3）如果次数为0，我们需要保存下一个数字，并把次数置1。因为次数为0，表示前面是字符串计数抵消为0。
2.代码
public class Solution {
public int MoreThanHalfNum_Solution(int[] array) {
// 用于记录出现次数大于数组一半的数
int maxNum = array[0];
//进行判断
if(array.length==0)
return maxNum;
// 于当前记录的数不同的数的个数
int numCount = 1;
// 从第二个数开始向后找
for(int i=1;i<array.length-1;i++){
// 如果记录的值与统计值相等，记数值增加
if(array[i] == maxNum){
numCount++;
}else{
// 如果不相同就减少，相互抵消
numCount--;
// 如果记数为0
if(numCount == 0){
// 记录统计值
numCount = 1;
//重新记录一个数，假设它是出现次数大于数组一半的
maxNum = array[i];
}
}
}
int total = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == maxNum) total++;
}
// 如果出现次数大于数组的一半就返回对应的值
if (total * 2 <= array.length) {
return 0;
}
else return maxNum ;
}
}
参考https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163?answerType=1&f=discussion
https://www.jianshu.com/p/3eee67b41201
https://blog.csdn.net/u010312474/article/details/99583346
