微信红包

[编程题]微信红包

热度指数：34769 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

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

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

数据范围： $1 \le n \le 1000 \$ ,红包金额满足 $1 \le gift_i \le 100000\$

示例1

输入

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

输出

示例2

输入

[1,1,2,2,3,3],6

输出

算法知识视频讲解

白伟仝

发表于 2020-06-27 17:57:41

用Map或哈希来计数： import java.util.*; public class Gift { public int getValue(int[] gifts, int n) { Map<Integer, Integer> m = new 展开全文

yau_song

发表于 2022-12-01 22:24:22

思路1：HashMap计数利用Map的键唯一，值可以重复的原理。如果当前元素重复则把当前重复的元素当做键，值加一添加到map中。以此来统计重复元素的个数。如果某元素的值超过了长度一半就输出。public class Gift { public int getValue(int[] gifts 展开全文

unique琪殿

发表于 2023-07-06 12:32:29

1.解题要点：①使用Arrays.sort()方法，将gifts数组按从小到大的顺序排序。②因为所求红包金额res出现的次数需超过红包总数的一半，则排序后的中间值必定为所求值(所求值存在的情况下)。③若循环结束后count <= n/2，则所求值不存在，返回0。2.完整代码： import j 展开全文