首页 > 代码库 > 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：如果有一个数组的出现次数超过一半，则必然有连着的两个相等的数。如果我们将连着的不相等的数都除去，剩余的就是相等的啦。
public int MoreThanHalfNum_Solution(int [] array) { int i; if(array.length == 1) return array[0]; if(array.length == 0) return 0; for( i=0;i<=(array.length-1)/2;i=i+2){ if(array[i]==array[i+1]){ break; } } if(i<=(array.length-1)/2){ return array[i]; }else{ if(array[i] == array[i-1]){ return array[i]; }else{ return 0; } } }
另一种代码是：
public int MoreThanHalfNum_Solution(int [] array) { int count = 0; int temp = 0; for(int i=0;i<array.length;i++){ if(count == 0){ temp = array[i]; count=1; }else{ if(array[i] == temp){ count++; }else{ count--; } } } int num = 0; for(int i=0;i<array.length;i++){ if(array[i] == temp){ num++; } } if(num>(array.length/2)){ return temp; }else{ return 0; } }
数组中出现次数超过一半的数字
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。