方法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。

02-13 05:44