Ebay OA 面试真题解析：多有序数组中查找第 K 小元素（Kth Element）

题目描述

给定 n 个有序数组，求这些数组中所有元素合并后第 k 小的元素。数组各自有序，整体不要求合并成一个大数组。

解题思路

把「每个数组当前指向的元素」放进最小堆，堆元素为 (值, 数组号, 下标)。每次弹出堆顶后，若该数组还有下一个元素就压入堆。重复 k 次，第 k 次弹出的值就是第 k 小。这是典型的多路归并。

import heapq

def kth_element(arrays, k):
    heap = []
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    for _ in range(k):
        val, i, j = heapq.heappop(heap)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j + 1], i, j + 1))
    return val

复杂度与易错点

堆大小 O(n)，共 k 次弹出压入，时间 O(k log n)。每个数组可能为空，空数组不要入堆；k 大于总元素数时按题面约定返回哨兵或报错。

FAQ

为什么堆里要同时存值和数组号、下标？

只存值无法知道弹出后该补入哪个数组的下一个元素；带上 (数组号, 下标) 才能正确推进归并指针。

参考来源

• LeetCode 23 — Merge k Sorted Lists
• LeetCode 378 — Kth Smallest Element in a Sorted Matrix

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。