Meta OA 面试真题解析：Top K Frequent Elements 与 Kth Smallest Element in a Sorted Matrix

Top K Frequent Elements

Description:

Given a non-empty array of integers, return up to k most frequent elements.

For example:

• Given [1,2,1,1,2,3] and k = 2, return [1,2].
• Given [1,1,1,1] and k = 1, return [1].
• Given [3,2,1,2,3] and k = 2, return [2,3].
• Given [1,2,3,4] and k = 2, return [1,2].

Assume valid k and valid integers.

Kth Smallest Element in Sorted Matrix

Description:

Given an n x n matrix where each of the rows and columns are sorted in non-decreasing order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [[1, 5, 9],
  [10, 11, 13],
  [12, 13, 15]
]

If k = 1, return 1.
If k = 2, return 5.
If k = 8, return 13.

Note: You may assume k is always valid, 1 <= k <= n^2.

Restriction:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n^2

这道题包含两个经典面试题：Top K Frequent Elements 和有序矩阵中的第 k 小元素。前者通常用哈希表统计频次，再结合堆、桶排序或快速选择在 O(n log k) 或更优的时间内取出前 k 个高频元素；后者因为矩阵的行和列都单调有序，常见做法是对值域二分，配合从右上角或左下角线性计数，判断不大于 mid 的元素个数是否达到 k，从而找到第 k 小值。面试中重点考察的是对“频率统计 + Top K”和“有序矩阵二分 + 计数”的组合思路，以及在约束 n ≤ 300 时如何选择稳定高效的实现。