腾讯笔试题 微信红包
首先,我们可以使用哈希表来记录每个红包金额出现的次数。遍历所有红包金额,将其作为键存入哈希表中,值为该金额出现的次数。然后再遍历哈希表,找到出现次数超过红包总数一半的金额即可。
具体算法思路如下:
1. 遍历所有红包金额,将其存入哈希表中,并记录出现次数。
2. 再次遍历哈希表,找到出现次数超过红包总数一半的金额。
3. 返回该金额作为结果。
下面是代码实现:
```pythondef find_majority_amount(red_packets):
创建哈希表 amount_count = {}
遍历红包金额,记录出现次数 for amount in red_packets:
if amount in amount_count:
amount_count[amount] +=1 else:
amount_count[amount] =1 找到出现次数超过红包总数一半的金额 for amount, count in amount_count.items():
if count > len(red_packets) //2:
return amount return None 测试red_packets = [10,20,10,30,10,10]
result = find_majority_amount(red_packets)
if result:
print("小明收到的红包金额超过一半的是:", result)
else:
print("没有找到符合条件的红包金额")
```
以上算法的时间复杂度为O(n),其中n为红包总数。通过哈希表记录红包金额出现次数,再遍历哈希表找到符合条件的金额,算法效率较高。希望对您有所帮助。