当前位置:网站首页>剑指offer之打印超过数组一半的数字

剑指offer之打印超过数组一半的数字

2020-11-09 22:18:50 龙韬

问题描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

解题思路

该问题有很多种解法,其中包括了使用HashMap、排序与候选法进行解题。
这里主要是讲解有关于使用候选法来解决这道算法问题。

候选法

一开始,我在看到这个问题的第一反映是通过哈希表来解决这个问题。当我使用了HashMap方法解决了这个问题之后,我觉得这道题应该不是考察使用哈希表来解决的。

所以,我就查看了题解,在官方的题解方法中,看到了候选的方法,具体的候选法的思路如下所示:

  1. 首先,设置候选者cnt=-1,并且设置候选数为count = 0
  2. 然后遍历整个数组。判断如果候选数0,则将候选者设置为当前数字;如果候选数大于0,则判断当前值是否与候选数相同,如果相同,则将候选数count++; 如果不相同,则将count--;
  3. 遍历完数组后,剩下的cnt为临时众数。需要再重新遍历一次数组,判断cnt的出现次数是否查过数组长度的一般。

算法的实现过程

使用HashMap方法

因为使用该方法过于简单,所以我就不再讲解这个解题的思路。

public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0) return 0;
        int len = array.length;
        int mid = len / 2;
        // 建立HashMap存储该数组中的位数,只需要遍历一次即可
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<len; i++){
            int m = array[i];
                map.put(m, map.getOrDefault(m, 0)+1);
        }
        for(int key: map.keySet()){
            if(map.get(key) > mid) return key;
        }
        
        return 0;
    }

使用候选法求解

//候选法,如果一个数为众数,那么这个数一定比其他的数存在的更多,可以抵消掉其他的数
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length ==0 ) return 0;
        int len = array.length;
        int mid = len/2;
        int cnt = -1;
        int count = 0;
        
        //首先遍历数组,找出众数
        for(int i=0; i<len; i++){
            if(count == 0){
                cnt = array[i];
                count ++;
            }else{
                if(cnt == array[i]){
                    count ++;
                }else{
                    count --;
                }
            }
        }
        
        //获得到众数,然后判断众数的个数是否大于数组的一半
        count = 0;
        for(int i=0; i<len; i++){
            if(cnt == array[i]) count ++;
        }
        
        if(count > mid) return cnt;
        else return 0;
        
    }

版权声明
本文为[龙韬]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/liulongtao/p/13950980.html