解题思路

这是一个查找众数的问题。具体要求：

  1. 给定一个数组表示红包金额
  2. 找出出现次数超过数组长度一半的金额
  3. 如果不存在这样的金额，返回0

解决方案：

  1. 先对数组排序
  2. 中位数是可能的候选项（因为如果一个数出现超过一半，一定会占据中位数位置）
  3. 统计中位数在数组中的出现次数
  4. 如果出现次数大于 ，则返回该数，否则返回

代码

class Gift {
public:
    int getValue(vector<int> gifts, int n) {
        // 排序数组
        sort(gifts.begin(), gifts.end());
        
        // 获取中位数
        int candidate = gifts[n/2];
        int count = 0;
        
        // 统计中位数出现次数
        for(int i = 0; i < n; i++) {
            if(gifts[i] == candidate) {
                count++;
            }
        }
        
        // 判断是否超过一半
        return count > n/2 ? candidate : 0;
    }
};

import java.util.*;

public class Gift {
    public int getValue(int[] gifts, int n) {
        // 排序数组
        Arrays.sort(gifts);
        
        // 获取中位数
        int candidate = gifts[n/2];
        int count = 0;
        
        // 统计中位数出现次数
        for(int gift : gifts) {
            if(gift == candidate) {
                count++;
            }
        }
        
        // 判断是否超过一半
        return count > n/2 ? candidate : 0;
    }
}

class Gift:
    def getValue(self, gifts: List[int], n: int) -> int:
        # 排序数组
        gifts.sort()
        
        # 获取中位数
        candidate = gifts[n//2]
        count = 0
        
        # 统计中位数出现次数
        for gift in gifts:
            if gift == candidate:
                count += 1
        
        # 判断是否超过一半
        return candidate if count > n//2 else 0

算法及复杂度

  • 算法：排序 + 计数
  • 时间复杂度： - 主要是排序的时间复杂度
  • 空间复杂度： - 只需要常数空间存储计数器