- 正确答案：可以使用快速选择算法（QuickSelect）在平均O(n)时间复杂度内求出数组中前K大的数（不要求顺序），其核心是基于快排的分区思想，只递归处理包含第K大元素的那个子区间；也可用最小堆（大小为K）维护当前遇到的最大的K个数，时间复杂度O(n log K)，空间复杂度O(K)；当K很小（如K=1, K=5）时，堆方法更稳定；当K接近n（如K=n/2）时，快速选择更优。 - 解答思路：题目只要求“前K大的数”，不要求有序，因此无需完整排序。首先明确“前K大”即第1大、第2大……第K大，等价于找出数组中第K大的元素（记为pivot），然后收集所有≥pivot的数（注意需处理重复值）。关键挑战在于：若直接排序（如快排或堆排）得O(n log n)，浪费；应降维打击——只定位到第K大元素的位置，并划分出至少K个不小于它的数。快速选择通过每次partition将数组划分为> pivot、= pivot、< pivot三部分（三路快排思想），精准收缩搜索区间；而堆方法则用容量为K的最小堆动态筛选：遍历数组，比堆顶大就替换堆顶并调整，最终堆中即为前K大。 - 深度知识讲解： 1. 快速选择的底层原理是分治+随机化+三路划分。标准partition（双指针）只能分出≤和≥两部分，但存在大量重复元素时会退化（如全相同数组导致O(n²)）。因此工业级实现必须采用三路划分（Dutch National Flag）：将数组原地划分为 > pivot | == pivot | < pivot 三个区间，返回等于区间的左右边界 [lt, gt]。这样可精确判断第K大落在哪个区间：设数组长度为n，第K大即升序下标为n−K的位置（0-indexed），若n−K ∈ [lt, gt]，则pivot就是答案；若n−K < lt，递归左半；若n−K > gt，递归右半。该优化使最坏情况期望仍为O(n)，且对重复数据鲁棒。 2. 最小堆方案本质是优先队列的应用。Java中用PriorityQueue（默认小根堆），Python中用heapq（最小堆），需手动维护大小：初始空堆，遍历每个数x，若堆尺寸 heap[0]（堆顶），pop再push(x)。注意：堆中元素不保证顺序，但堆顶始终是当前K个数中最小者，因此能确保所有入堆元素都≥堆顶，最终堆内即为全局前K大。其正确性依赖于“贪心+淘汰”策略：每一步都保留当前看到的最大K个候选。 3. 空间与稳定性权衡：快速选择可原地进行（O(1)额外空间），但会修改原数组；堆方法需O(K)空间，但不破坏输入。若要求不修改原数组且K较小，堆更合适；若内存敏感且允许修改，快速选择最优。 4. 其他方法对比： • 计数排序：仅适用于数值范围小且为整数的情形（如0~1000），时间O(n + range)，但空间O(range)； • BFPRT算法（中位数的中位数）：理论最坏O(n)，但常数极大，实际远慢于随机化快速选择，面试中一般不需实现，但需知道存在确定性线性解。 - 伪代码（快速选择，三路划分，返回前K大数的集合）： ``` function topKByQuickSelect(arr, K): if K <= 0 or K > length(arr): return empty list n = length(arr) // 第K大对应升序索引 pos = n - K pos = n - K copy = arr.copy() // 避免修改原数组 quickSelect(copy, 0, n-1, pos) // 收集所有 >= copy[pos] 的元素（需去重计数，因可能有多个等于copy[pos]的数） pivot = copy[pos] result = [] countPivotNeeded = K for i from 0 to n-1: if copy[i] > pivot: append copy[i] to result countPivotNeeded-- // 补齐等于pivot的数，最多补countPivotNeeded个 for i from 0 to n-1: if countPivotNeeded <= 0: break if copy[i] == pivot: append pivot to result countPivotNeeded-- return result function quickSelect(arr, lo, hi, k): if lo >= hi: return // 三路划分：返回[lt, gt]，满足 arr[lo..lt-1] > pivot, arr[lt..gt] == pivot, arr[gt+1..hi] < pivot (lt, gt) = threeWayPartition(arr, lo, hi) if k < lt: quickSelect(arr, lo, lt-1, k) else if k > gt: quickSelect(arr, gt+1, hi, k) function threeWayPartition(arr, lo, hi): pivot = arr[lo] lt = lo // arr[lo+1..lt] > pivot i = lo + 1 // arr[lt+1..i-1] == pivot gt = hi + 1 // arr[gt..hi] < pivot while i < gt: if arr[i] > pivot: swap arr[lt], arr[i] lt++ i++ else if arr[i] < pivot: gt-- swap arr[i], arr[gt] else: i++ return (lt, gt-1) ``` - 伪代码（最小堆法，推荐用于面试简洁实现）： ``` function topKByHeap(arr, K): if K <= 0: return empty list minHeap = new MinHeap() for x in arr: if size(minHeap) < K: minHeap.push(x) else if x > minHeap.top(): minHeap.pop() minHeap.push(x) return minHeap.toArray() // 堆中元素即为前K大，顺序任意 ``` 注：MinHeap可用数组模拟，push/pop时间O(log K)，总时间O(n log K)；实际编码中可直接调用语言内置堆（如Python heapq.heapify + heappush/heappop，注意heapq是最小堆，需存负数变最大堆，但更推荐直接用正数+条件判断，避免取反开销）。 - 扩展知识：该问题在大数据场景中演变为“Top-K流式计算”，需结合蓄水池抽样（Reservoir Sampling）或近似算法（如Count-Min Sketch）；在分布式系统中，常采用MapReduce两轮：Map端局部Top-K，Reduce端合并全局Top-K。面试中若被追问扩展，可简述这些方向以体现工程视野。

腾讯自然语言处理(NLP) 暑期实习二面

全站热榜

创作者周榜