- 正确答案：TOP K大的数问题是指在无序数组中找出最大的K个元素（不一定要排序输出）。最优解法是使用最小堆（大小为K的优先队列）或快速选择算法（QuickSelect），时间复杂度分别为O(n log k)和平均O(n)。当k远小于n时，堆方法更稳定且易于实现；当k接近n或需极致性能时，QuickSelect更优。 - 解答思路：思路一（最小堆法）：维护一个容量为K的最小堆。遍历数组，对每个元素：若堆未满，直接插入；若堆已满且当前元素大于堆顶，则弹出堆顶并插入当前元素。最终堆中即为TOP K大的数（堆顶为其中最小者）。思路二（QuickSelect）：基于快排分区思想，随机选pivot，将数组划分为> pivot、= pivot、< pivot三部分（三路划分可避免重复元素退化）。若大于pivot的元素个数 ≥ K，则在右段递归；若大于+等于 ≥ K但大于 < K，则返回等于部分（需去重或计数）；否则在左段找剩余K' = K - (大于+等于)个。只需处理一个子区间，故期望时间复杂度O(n)。 - 深度知识讲解： 1. 堆的本质是完全二叉树的数组表示：对于索引i，左孩子为2*i+1，右孩子为2*i+2，父节点为(i-1)//2。最小堆满足arr[i] ≤ arr[2*i+1]且arr[i] ≤ arr[2*i+2]。Python中heapq模块仅提供最小堆，模拟最大堆需存入负值。 2. 堆插入/删除时间复杂度为O(log k)，共n次操作 → O(n log k)；空间复杂度O(k)。 3. QuickSelect是BFPRT（中位数的中位数）算法的简化版，其最坏时间复杂度为O(n²)，但通过随机化pivot可使期望复杂度为O(n)，且常数因子小。关键在于partition过程必须原地进行（节省空间），且支持三路划分（处理重复元素）。三路划分将数组分为[>pivot, ==pivot, pivot与low交换并双增，遇==pivot仅mid++，遇 len(nums): return [] heap = [] for num in nums: if len(heap) < k: heapq.heappush(heap, num) elif num > heap[0]: heapq.heapreplace(heap, num) # 等价于pop+push，更高效 return heap # 无序，若需升序返回则sorted(heap)，降序则sorted(heap, reverse=True) - 代码示例（QuickSelect三路划分，Python）： import random def top_k_largest_quickselect(nums, k): if not nums or k <= 0 or k > len(nums): return [] arr = nums.copy() def partition_3way(left, right): # 随机选pivot并换到right位置 idx = random.randint(left, right) arr[idx], arr[right] = arr[right], arr[idx] pivot = arr[right] lt, gt = left, right # arr[left+1:lt+1] > pivot, arr[gt:right] < pivot i = left while i <= gt: if arr[i] > pivot: arr[i], arr[lt] = arr[lt], arr[i] lt += 1 i += 1 elif arr[i] < pivot: arr[i], arr[gt] = arr[gt], arr[i] gt -= 1 else: i += 1 return lt, gt # [left, lt) > pivot, [lt, gt+1) == pivot, (gt, right] < pivot def quickselect(left, right, k_target): if left >= right: return lt, gt = partition_3way(left, right) greater_count = lt - left equal_count = gt - lt + 1 if greater_count >= k_target: quickselect(left, lt - 1, k_target) elif greater_count + equal_count >= k_target: return # 目标已覆盖，无需进一步处理小于pivot部分 else: quickselect(gt + 1, right, k_target - greater_count - equal_count) quickselect(0, len(arr) - 1, k) return arr[:k] # 前k个即为TOP K大（不保证内部顺序） - 扩展知识： • 流式数据场景（数据动态到达）：需用“败者树”或“双堆法”（大顶堆存小数，小顶堆存大数，维持小顶堆size=k）； • 分布式TOP K：MapReduce中Mapper输出(key,1)，Reducer聚合计数后用堆取Top K；Flink/Spark中可用approxQuantile近似计算，牺牲精度换性能； • 内存受限时：可采用外部排序或分块处理（如每块取局部Top K，再合并）； • 理论下界：基于比较的TOP K问题信息论下界为Ω(n + k log k)，最小堆法达到O(n log k)，QuickSelect接近下界（当k=O(n)时O(n)）。

字节电商推荐算法实习一面凉经

全站热榜

创作者周榜