题解| #数组中出现次数超过一半的数字#

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000
示例1
输入：[1,2,3,2,2,2,5,4,2]
返回值：2

题目分析

因为数组长度（length）是确定的，可以计算出数组长度的一半(length/2)是多少，直观的想，可以遍历数组，统计数字出现的次数，若是不小于length/2，即目标数字。

解题思路

方法1：使用hashMap，保存数字数值和出现次数，若是重复出现则将次数加1；

遍历最后结果

方法2：对数组排序，位于数组的中间下标的数字，就是目标数字；
排序后数组显示：

代码实现

方法一：哈希法

 public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        if(array.length == 1) return array[0];
        // hashmap存储数字和它的出现次数
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0;i<array.length;i++){
            // 若map中没有，则放入hashmap，并将次数置为1
            if(!map.containsKey(array[i])){
                map.put(array[i],1);
            }else if(map.get(array[i]) < array.length/2){
                // 若map中有，且次数少于一半，就将map中的次数加1
                map.put(array[i],map.get(array[i])+1);
            }else{
                // 若map中有，且次数多于或等于一半，则直接返回该数
                return array[i];
            }
        }
        return 0;
    }

时间复杂度：O(n)，其中 n 是数组 array 的长度。遍历数组 array 一次，对于 array 中的每一个元素，获取哈希表中的值以及将其插入哈希表都只需要常数时间，因此时间复杂度为 O(n)。
空间复杂度：O(n)，哈希表最多存储 n/2 个数据，因此空间复杂度为 O(n)。

方法二：数组排序

 public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        if(array.length == 1) return array[0];
        // 快速排序
        Arrays.sort(array);
        // 返回数组的中间值
        return array[array.length/2];
}

时间复杂度：因为使用了Arrays.sort()方法，实现的是快速排序，所以时间复杂度为O(nlogn)，相比哈希法要消耗更多的时间。
空间复杂度：若是题目明确要求不能改变原来的数组，则需要创建一个新的与原来的数组一样的数组，空间复杂度O(n)，若是没有要求，则可以直接在原来的数组上修改，空间复杂度O(1)。