- 正确答案：使用自定义比较器对商品集合进行排序，按热度降序为主键、销量降序为次键，然后取前N个元素；时间复杂度O(M log M)，空间复杂度O(1)（若原地排序）或O(M)（若拷贝后排序）。最优解可采用堆优化至O(M log N)，尤其当N << M时更高效。 - 解答思路：第一步：明确排序规则——热度优先降序（高热度排前面），热度相同时销量降序（高销量排前面）；第二步：考虑数据规模与约束：若M较大而N很小（如M=10^6，N=10），全量排序浪费性能，应改用大小为N的最大堆（或最小堆+逆向逻辑）维护Top-N；第三步：实现策略分两种：（a）通用简洁法：Arrays.sort + 自定义Comparator，适合校园招聘中代码清晰性与正确性优先的场景；（b）进阶优化法：使用PriorityQueue构建容量为N的最小堆，遍历每个商品，若堆未满则入堆；若堆已满且当前商品比堆顶“更大”（即更应入选Top-N），则弹出堆顶并插入当前商品。注意：堆中需按“热度升序、销量升序”维护最小值，从而保证堆顶是当前Top-N中最弱者，便于淘汰。第四步：输出结果需按Top-N从高到低排列，故最终将堆中元素导出后需反转（因最小堆自然有序是升序，而我们要热度从高到低）。 - 深度知识讲解：【底层比较逻辑】Java中Comparator.compare(a,b)返回负数表示a b.heat时应返回负数。完整逻辑： if (a.heat != b.heat) return Integer.compare(b.heat, a.heat); // 降序：b.a - a.a 等价于 -(a-b) else return Integer.compare(b.sales, a.sales); // 销量也降序【堆优化原理】Top-K问题本质是流式数据中维护K个极值。最小堆能以O(log K)完成每次更新，总时间O(M log K)。其关键在于堆顶代表当前K个候选中最不满足条件者（即阈值），所有比它“更强”的新元素才有资格替换它。这里“强”定义为：(heat, sales) 字典序更大（先比heat，再比sales），因此堆必须按字典序升序排列（使堆顶为字典序最小者），才能正确淘汰。【稳定性与对象引用】若商品类存在重复对象或需保持原始索引，需注意：Arrays.sort使用的是双轴快排（Java 7+），对于对象数组是稳定排序（相同键值相对顺序不变）；而PriorityQueue基于二叉堆，不保证稳定性，若需稳定Top-K，应在比较器中加入原始下标作为第三级比较（但本题未要求，通常忽略）。【内存与GC考量】若M极大（如千万级），避免一次性加载全部商品到内存；可考虑外部排序或分块处理，但校招题默认内存充足。【泛型与函数式写法】Java 8+推荐使用Lambda表达式简化Comparator： Comparator cmp = (a, b) -> { int heatDiff = Integer.compare(b.heat, a.heat); if (heatDiff != 0) return heatDiff; return Integer.compare(b.sales, a.sales); }; 【边界处理】需检查N > M时实际只返回M个；N ≤ 0时返回空列表；商品集合为null时抛NullPointerException或防御性返回空列表（根据题目约定）。 - 伪代码（堆优化版，推荐用于M大N小场景）： ``` List topNProducts(List products, int N) { if (products == null || N <= 0) return new ArrayList<>(); if (N >= products.size()) return new ArrayList<>(products); // 可直接排序返回 // 最小堆：按(heat, sales)升序排列 → 堆顶是Top-N中最弱者 PriorityQueue minHeap = new PriorityQueue<>((a, b) -> { int heatDiff = Integer.compare(a.heat, b.heat); if (heatDiff != 0) return heatDiff; return Integer.compare(a.sales, b.sales); }); for (Product p : products) { if (minHeap.size() < N) { minHeap.offer(p); } else if (isStrongerThan(p, minHeap.peek())) { minHeap.poll(); minHeap.offer(p); } } // 导出并反转：因堆是最小堆，导出是升序（弱→强），需反转为强→弱 List result = new ArrayList<>(minHeap); Collections.reverse(result); return result; } // 辅助方法：判断p是否比q更强（即p应排在q前面） boolean isStrongerThan(Product p, Product q) { if (p.heat > q.heat) return true; if (p.heat < q.heat) return false; return p.sales > q.sales; // 热度相同时销量更高者更强 } ``` - 代码示例（Java完整可运行版本，含商品类定义）： ``` class Product { int heat; int sales; Product(int heat, int sales) { this.heat = heat; this.sales = sales; } @Override public String toString() { return String.format("Product{heat=%d, sales=%d}", heat, sales); } } import java.util.*; public class TopNProducts { public static List getTopN(List products, int N) { if (products == null || N <= 0) return Collections.emptyList(); if (N >= products.size()) { // 全排序并按规则降序 products.sort((a, b) -> { int h = Integer.compare(b.heat, a.heat); if (h != 0) return h; return Integer.compare(b.sales, a.sales); }); return products; } PriorityQueue heap = new PriorityQueue<>((a, b) -> { int h = Integer.compare(a.heat, b.heat); if (h != 0) return h; return Integer.compare(a.sales, b.sales); }); for (Product p : products) { if (heap.size() < N) { heap.offer(p); } else { Product top = heap.peek(); if (p.heat > top.heat || (p.heat == top.heat && p.sales > top.sales)) { heap.poll(); heap.offer(p); } } } List res = new ArrayList<>(heap); res.sort((a, b) -> { int h = Integer.compare(b.heat, a.heat); if (h != 0) return h; return Integer.compare(b.sales, a.sales); }); return res; } } ``` - 扩展知识点：【Top-K变体】若要求“热度前N，销量前N分别独立”，则是两个单维度Top-K；若要求“热度和销量加权得分Top-N”，则需预计算score = w1*heat + w2*sales；若数据实时流入（流式Top-K），可用Lossy Counting或Space-Saving算法近似求解。【工程实践】真实电商系统中，热度可能含时间衰减因子（如热度 = 原始销量 * e^(-λt)），需在比较前预处理；排序常由ES或Redis ZSET完成，Java层仅做轻量聚合。【面试追问点】面试官可能追问：如何支持动态更新商品热度？→ 引入堆的删除操作（需支持decrease-key，Java PriorityQueue不直接支持，需用HashMap记录位置+惰性删除）；或改用TreeSet+自定义比较器（支持O(log K)增删，但需确保对象不可变或谨慎处理修改）。

字节中国交易与广告一面

全站热榜

创作者周榜