题解 | #微信红包#

思路1：HashMap计数

利用Map的键唯一，值可以重复的原理。

如果当前元素重复则把当前重复的元素当做键，值加一添加到map中。以此来统计重复元素的个数。

如果某元素的值超过了长度一半就输出。

public class Gift {
    public int getValue(int[] gifts, int n) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < gifts.length; i++){
            if(map.containsKey(gifts[i])){
                map.put(gifts[i],map.get(gifts[i]) + 1);
            } else {
                map.put(gifts[i], 1);
            }
            if(map.get(gifts[i]) > gifts.length >> 1) {
                return gifts[i];
            }
        }
        return 0;
 	}
}

思想2：

这是一个经典的水王问题的变形。大家可以参考左神的视频讲解。

https://www.bilibili.com/video/BV1kR4y1K7Zm/?share_source=copy_web&vd_source=1679b6c6e679ee3d744792e499f95a0d

public class Gift {
    public int getValue(int[] gifts, int n) {
		int candidate = 0;
		int hp = 0;
		for(int i = 0; i < n; i++){
			if(hp == 0){
				candidate = gifts[i];
				hp++;
			} else if(gifts[i] == candidate){
				hp++;
			} else if(gifts[i] != candidate) {
				hp--;
			}
		}
		int count = 0;
		for(int item : gifts) {
			if(item == candidate) {
				count++;
			}
		}
		if(count > (n >> 1)) {
			return candidate;
		}
        return 0;
    }
}