微信红包找到出现次数大于一半的数

- 日理万妓 2022-07-16 04:10 200阅读 0赞

微信红包

*  热度指数：4204时间限制：3秒空间限制：32768K
 *  本题知识点： [查找][Link 1]
 *  [ 算法知识视频讲解][Link 2]

## 题目描述 ##

春节期间小明使用微信收到很多个红包，非常开心。在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。

给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。

若没有金额超过总数的一半，返回0。

测试样例：

[1,2,3,2,2],5

返回：2

import java.util.*;
    import java.util.Map.Entry;
    public class Gift {
        public int getValue(int[] gifts, int n) {
            Map<Integer,Integer> m = new HashMap<Integer,Integer>();
            for(int i=0;i<n;i++){
                if(m.containsKey(gifts[i])==false){
                    m.put(gifts[i],1);
                }else{
                    m.put(gifts[i],m.get(gifts[i])+1);
                }
            }
            for(Entry<Integer,Integer> e : m.entrySet()){
                if(e.getValue()>n/2)return e.getKey();
            }
            return 0;
        }
    }

或者用删除不同数的方法

问题其实就是求一个数组中出现次数超过一半的数，用哈希表可以解决问题，但不是最优。
    注意某数出现超过一半，可以考虑在遍历数组时，每次删掉两个不同的数字，最后剩下的数就是我们的解.
    import java.util.*;
    public class Gift {
        public int getValue(int[] gifts, int n) {   
            int gift=-1,times=0;       
            for(int i=0;i<n;i++){
                if(times==0){
                    gift=gifts[i];
                }
                if(gift==gifts[i]){
                    times++;
                }else{
                    times--;
                }
            }
            //处理不存在出现次数超过一半的情况
            int count=0;
            for(int i=0;i<n;i++){
                if(gift==gifts[i]){
                    count++;
                }
            }
            return count>n/2?gift:0;
           
        }
    }

[Link 1]: http://www.nowcoder.com/questionCenter?questionTypes=000100&mutiTagIds=589
[Link 2]: http://www.nowcoder.com/courses/1