豆包MarsCode：小C点菜问题
问题描述
思路分析
这道题的核心任务是找出所有不超过给定价格 m 的菜肴中，最常见的菜肴价格，最后返回该价格的出现次数。
1. 题意理解：
- 给定一个最大价格
m，小C只会选择价格不超过m的菜。 - 菜单上有
n道菜，每道菜有一个价格，价格用数组w存储。 - 需要找出价格不超过
m的菜中，最多可以点多少道价格相同的菜。
2. 解题步骤：
- 过滤价格：首先，我们要从价格数组中筛选出所有小于或等于
m的价格，因为小C只会选择这些价格的菜。 - 统计频率：然后，对这些符合条件的菜的价格进行统计，找出每个价格出现的次数。
- 找出最大频率：最终，我们找出出现次数最多的价格，并返回这个最大次数。
3. 实现方法：
- 遍历菜肴价格：我们需要遍历菜单上的每道菜，检查价格是否小于或等于
m。如果符合条件，就记录下它的频率。 - 使用哈希表（HashMap）：我们使用一个哈希表来存储价格和对应的频率。哈希表的键是价格，值是该价格出现的次数。
- 找出最大值：遍历哈希表，找出出现次数最多的价格，最后返回该次数。
哈希表相关方法可见：一篇文章让你学会Java之哈希表操作
参考代码（Java）
import java.util.HashMap;
public class Main {
public static long solution(int m, int[] w) {
// 用于存储价格 <= m 的频率
HashMap<Integer, Integer> priceCount = new HashMap<>();
// 统计价格 <= m 的频率
for (int price : w) {
if (price <= m) {
priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);
}
}
// 找到最大频率
int maxCount = 0;
for (int count : priceCount.values()) {
maxCount = Math.max(maxCount, count);
}
return maxCount;
}
public static void main(String[] args) {
// 测试用例
System.out.println(solution(6, new int[]{2, 3, 3, 6, 6, 6, 9, 9, 23}) == 3);
System.out.println(solution(4, new int[]{1, 2, 4, 4, 4}) == 3);
System.out.println(solution(5, new int[]{5, 5, 5, 5, 6, 7, 8}) == 4);
}
}
代码分析
solution 方法：
这个方法的目的是根据给定的最大价格 m，在菜单价格数组 w 中找出价格不超过 m 的菜肴，统计每个价格的出现次数，然后返回出现次数最多的菜肴的价格出现次数。
-
输入参数：
m: 这是小C可以接受的最大价格。w: 一个整数数组，代表餐馆菜单中每道菜的价格。
-
返回值：
- 返回一个整数，表示价格最常出现的次数。
1. 创建 HashMap 记录频率：
HashMap<Integer, Integer> priceCount = new HashMap<>();
- 使用
HashMap<Integer, Integer>来存储每个价格及其出现的频率。键是菜品的价格，值是该价格出现的次数。
2. 遍历价格数组 w 并统计频率：
for (int price : w) {
if (price <= m) {
priceCount.put(price, priceCount.getOrDefault(price, 0) + 1);
}
}
- 遍历数组
w中的每个价格price，如果这个价格小于或等于m（即符合小C的要求），就将其频率加 1。 priceCount.getOrDefault(price, 0)表示如果price已经在priceCount中存在，则返回该价格的当前频率，否则返回默认值0。- 然后将该价格的频率更新为原来的频率加 1。
3. 找出最大频率：
int maxCount = 0;
for (int count : priceCount.values()) {
maxCount = Math.max(maxCount, count);
}
- 遍历
priceCount中的所有频率值，找到其中最大的频率。 Math.max(maxCount, count)用来更新maxCount，保留最大频率。
4. 返回最大频率：
return maxCount;
- 最后返回最大频率，即小C可以选择的最多价格相同的菜肴的数量。
总结：
- HashMap 用于统计频率：通过遍历菜品价格并更新每个价格的出现次数，使用
getOrDefault来确保价格不在priceCount中时，能够正确初始化为 0。 - 最大频率的查找：通过遍历哈希表的所有值，找到最大的频率，最后返回。
- 时间复杂度：遍历数组
w和哈希表的操作，整体时间复杂度是O(n)，其中n是菜单价格的数量。