题目:数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
//参数:给定数组
//题意:数组中仅有一个数字出现的次数超过了数组长度的一半,找出这个数字;如果没有,则返回0
//思路:利用另一道题目作为这道题目的基础,即:统计排序数组中指定数字的个数
//①:准备一个有序数组中统计指定数字个数的方法(参考剑指offer中的该题)
//②:因为本题只是找出该数字,所以跟该数字的索引位置并没有关系,于是将本题传入的参数数组排序
//③:遍历该数组中的元素,判断数量是否超过数组长度的一半,是就返回该元素;否则返回0即可
import java.util.Arrays; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { Arrays.sort(array); for(int i=0;i<array.length;i++){ if(getNumberOfK(array,array[i])>(array.length/2)){ return array[i]; } } return 0; } public int getNumberOfK(int[] array,int k){ //Arrays.sort(array); int index=Arrays.binarySearch(array,k); if(index<0){ return 0; } int cnt=1; for(int i=index+1;i<array.length&&array[i]==k;i++){ cnt++; } for(int i=index-1;i>=0&&array[i]==k;i--){ cnt++; } return cnt; } }