效率最高的解法
数组中出现次数超过一半的数字
http://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163
看到好多人用排序或者哈希表。其实没必要这么复杂，我们想，一个数组中有一个数字出现的次数，超过一半，那arr[half]必定是这个数字，其中half=arr.length/2。那这样就简单了，遍历一遍数组，统计arr[half]出现的次数，看是否超过数组长度的一半即可。代码如下：
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if (array==null||array.length==0)
return 0;
int half=array.length/2;
int num=array[half];
int count=0;
for (int item:array){
if (item==num)
++count;
}
if (count>half)
return num;
return 0;
}
}效率应该比排序或哈希表的时间和空间效率都要好得多。
投递微众银行等公司7个岗位 >
查看19道真题和解析