一 、题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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; } } }
