方法1:若出现次数过半则该数必定为中位数,因此,排序后统计中位数出现次数,过半则返回该数,否则返回0。
方法2:遍历统计每一个数字出现的次数,过半则返回该数,若全部遍历后无过半数,则返回0。考虑到数据范围可能很大,统计使用hashmap保存而不用数组。
public int moreThanHalfNum(int[] array) { int len = array.length; if(len == 1) return array[0]; Map<Integer,Integer> count = new HashMap<Integer,Integer>(); for(int i=0; i<len; i++) { if(count.containsKey(array[i])) { int value = count.get(array[i]); count.put(array[i], value+1); if(value+1 > len/2) return array[i]; } else count.put(array[i], 1); } return 0; }
方法3:若出现次数过半,则满足关系:出现次数 - 未出现次数 > 0,因此,可记录当前数字及出现次数,下一个数仍为该数则出现次数加一,否则减一,出现次数为0时更改当前数字为下一个数,最后重新统计最终记录的数字出现的次数,若过半则返回,否则返回0。