本题为：剑指offer面试题29
牛客网测试地址：https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
时间限制：1秒 空间限制：32768K算法知识视频讲解 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。Java代码如下：
package go.jacob.day504; public class Demo1 { /* * 方法1：如果输入数组符合要求，那么所求数字的出现次数要多于其他所有数字次数之和 * 该方法不需要对输入数组进行操作 */ public int MoreThanHalfNum_Solution(int[] array) { if(array==null) return 0; int N=array.length; int root=0; int count=0; for(int i=0;i<N;i++){ if(count==0){ root=array[i]; count=1; } if(array[i]==root){ count++; }else{ count--; } } //判断数组中书否存在出现次数大于一半的数字 if (checkArray(array, root)) { return root; } else return 0; } /* * 方法二：利用快速排序的partition方法找到处于N/2位置的元素，如果输入数组符合要求 * 那么该元素即为所求数字 * 该方法会对输入数组进行操作，面试时应该询问面试官能否允许。 */ public int MoreThanHalfNum_Solution_1(int[] array) { //判空 if (array == null) return 0; int N = array.length; int middle = N / 2; int index = partition(array, 0, N - 1); while (index != middle) { if (index > middle) { index = partition(array, 0, index - 1); } else index = partition(array, index + 1, N - 1); } // 判断数组是否存在出现次数超过一般的数字 if (checkArray(array, array[index])) { return array[index]; } else return 0; } //快速排序中的partition方法 private int partition(int[] array, int left, int right) { // 判断数组是否只有一个元素 if (left == right) return left; int root = array[left]; int i = left, j = right + 1; while (true) { while (array[++i] <= root) { if (i == right) break; } while (array[--j] >= root) { if (j == left) break; } if (i < j) exch(array, i, j); else break; } exch(array, left, j); return j; } //检查数组是否存在出现次数超过一半的数字 private boolean checkArray(int[] array, int root) { int N = array.length; int num = 0; for (int i = 0; i < N; i++) { if (array[i] == root) { num++; } } if (num * 2 > N) return true; else return false; } private void exch(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } }
