一 、题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
二、 题目分析
- 这个数字存在次数一定是最多的，我们可以用守擂法
- 定义一个num(代表当前的数字)和sum(代表当前的次数)
- 如果遇见一样的，就进行sum++，不一样的就sum–,同时要看sum的值，如果sum为0的话，表示这个数字不是我们要找的，需要将num的值进行替换
- 最后，重新遍历一遍数组，找出这个最多存在次数的数字的存在次数（count），将count与array.length进行对比，得出最后的结果。
三、题目代码
package offer;
public class Test26 {
/*
* 题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
* 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 如果不存在则输出0。
*/
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
int x = MoreThanHalfNum_Solution(array);
System.out.println(x);
}
public static int MoreThanHalfNum_Solution(int[] array) {
if (array.length == 0 || array == null) {
return 0;
}
// 采取守擂法
int num = array[0]; // 代表当前的数字
int sum = 0; // 代表当前的次数
for (int i = 0; i < array.length; i++) {
if (array[i] != num) {
if (sum > 0) {
sum--;
} else {
num = array[i];
}
} else {
sum++;
}
}
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == num) {
count++;
}
}
if (count > array.length / 2) {
return num;
} else {
return 0;
}
}
}