- 正确答案：求前K小的数有多种解法，最优解取决于数据规模和约束条件。在校园招聘面试中，通常考察候选人对不同算法的时间/空间复杂度权衡、底层原理理解及工程取舍能力。主流解法包括：（1）排序后取前K个（O(n log n)时间，简单但非最优）；（2）堆优化——维护大小为K的最大堆（O(n log k)时间，O(k)空间，推荐用于k << n场景）；（3）快速选择算法（QuickSelect，平均O(n)，最坏O(n²)，原地、不稳定性可接受，理论最优）；（4）BFPRT算法（中位数的中位数，严格O(n)最坏时间，但常数大，极少手写）。面试中若未限定“必须最优”，应优先实现最大堆解法；若强调“最优平均性能”或“原地”“不额外空间”，则应实现QuickSelect并能分析其划分过程。 - 解答思路：第一步：明确问题定义——给定无序数组arr和正整数k（1 ≤ k ≤ n），返回任意一个包含前K小元素的集合（不要求有序，但常见要求是“返回这K个数”，部分题要求升序排列，需确认）。第二步：评估候选方案。排序法虽直观，但做了多余工作（全排序）；堆法利用“只需维护K个最小候选”的直觉，用最大堆淘汰大数；QuickSelect则借鉴快排分区思想，每次partition将数组划分为< pivot、= pivot、> pivot三段，根据左段大小决定向左或向右递归，从而避免全排序。第三步：选择实现策略。堆解法逻辑清晰、边界安全、易调试，适合笔试/白板；QuickSelect需处理重复元素、pivot选择、区间闭合等细节，但体现算法深度。建议先写堆解法，再主动提出QuickSelect优化，并分析优劣。 - 深度知识讲解：【1】最大堆的底层实现原理：堆是完全二叉树的数组表示。对于0-indexed数组heap，节点i的左子节点索引为2*i+1，右子节点为2*i+2，父节点为(i-1)//2。最大堆满足：heap[i] ≥ heap[2*i+1] 且 heap[i] ≥ heap[2*i+2]。插入时在末尾添加，然后向上调整（sift-up）；弹出最大值时交换首尾，删除末尾，再向下调整（sift-down）。手写堆不必完整实现Heap类，可用Python heapq（但注意：heapq是最小堆，因此存入负值模拟最大堆，或用heapq.nlargest/k，但面试要求“手撕”，需自己维护逻辑）。【2】QuickSelect的核心机制与数学保证： QuickSelect是基于分治的随机化算法。每次随机选pivot，partition后得到left_len = 左侧元素个数（即 < pivot 的数量），mid_len = 等于pivot的数量。若 left_len ≥ k，则第k小在左侧；若 left_len + mid_len ≥ k，则pivot本身即为第k小；否则在右侧递归找第 (k − left_len − mid_len) 小。其期望时间复杂度为O(n)，因为每次平均丢弃一半数据：T(n) = T(n/2) + O(n) ⇒ T(n) = O(n)。最坏情况（每次选到极值pivot）为O(n²)，可通过随机化pivot或BFPRT避免。注意：partition必须是原地、稳定划分（如Lomuto或Hoare分区方案），且要正确处理重复元素——推荐三路快排分区（Dutch National Flag），将数组分为 < pivot | == pivot | > pivot 三段，避免重复递归。【3】空间与稳定性考量：堆解法空间复杂度O(k)，适合内存受限且k很小时（如TopK日志、流式TopK）；QuickSelect原地O(1)额外空间（不计递归栈），但会修改原数组；若要求不修改输入，需拷贝——此时空间为O(n)。两者均不稳定（相等元素相对顺序可能改变），但前K小问题本身不要求稳定性。 - 代码示例（两种解法均提供，以Python伪代码风格书写，符合手写规范）：【解法一：最大堆（推荐首选）】 def top_k_smallest_heap(arr, k): if k == 0: return [] import heapq max_heap = [] # 存负值模拟最大堆 for num in arr: if len(max_heap) < k: heapq.heappush(max_heap, -num) elif num < -max_heap[0]: # 当前数比堆顶（当前第k小的最大值）还小 heapq.heapreplace(max_heap, -num) # 弹出最大，压入新数 return sorted([-x for x in max_heap]) # 若要求升序输出，最后排序；否则直接返回[-x for x in max_heap] 【解法二：QuickSelect（三路分区版）】 import random def top_k_smallest_quickselect(arr, k): if k == 0: return [] nums = arr[:] # 不修改原数组 def partition_3way(left, right): # 随机选pivot并换到right位置 idx = random.randint(left, right) nums[idx], nums[right] = nums[right], nums[idx] pivot = nums[right] lt, gt = left, right # nums[left+1:lt+1] < pivot; nums[gt:right] > pivot i = left while i <= gt: if nums[i] < pivot: nums[i], nums[lt] = nums[lt], nums[i] lt += 1 i += 1 elif nums[i] > pivot: nums[i], nums[gt] = nums[gt], nums[i] gt -= 1 else: i += 1 return lt, gt # [left, lt) < pivot; [lt, gt+1) == pivot; (gt, right] > pivot def quickselect(left, right, kth): # 找整个数组中第kth小（1-indexed） if left >= right: return lt, gt = partition_3way(left, right) if kth <= lt - left: quickselect(left, lt - 1, kth) elif kth > gt - left + 1: quickselect(gt + 1, right, kth - (gt - left + 1)) # 否则kth落在等于pivot区间，无需进一步操作 quickselect(0, len(nums)-1, k) return nums[:k] # 前k个即为前K小（不一定有序，但题目未要求有序时可直接返回）补充说明：若题目明确要求“返回升序的前K小”，则QuickSelect后对nums[:k]调用sort（O(k log k)），总复杂度仍为平均O(n)；堆解法则在返回前sorted()即可。 - 扩展知识：（1）流式场景：若数据是数据流（无限/动态到达），无法全部加载内存，则需使用Reservoir Sampling（不适用TopK）或动态堆（维护大小为K的最大堆，每来一个数判断是否替换堆顶），时间O(m log k)，m为总数据量。（2）外部排序：当数组远大于内存（如1TB数组，内存仅1GB），需结合外部归并排序 + 多路归并取前K。（3）并行化：QuickSelect可并行partition，但递归分支难负载均衡；堆法天然支持多线程批量插入（需加锁或并发堆）。（4）语言特性：C++ std::nth_element即QuickSelect实现；Java无直接对应，需手动；Python heapq.nsmallest(k, arr)内部自动选择算法（k小用堆，k接近n用排序）。面试中务必主动沟通：询问k是否远小于n？是否允许修改原数组？是否需要去重？是否要求结果有序？这些细节直接影响解法选择，体现工程素养。

搜推算法日常实习二面-美团

全站热榜

创作者周榜