特定公式生成的N*N网格中求第K小元素的高效解法

问题分析 #

给定N * N网格，每个元素的计算公式为A[i][j] = (i + j)² + (j - i) * 10^5，约束下N最大可达5*10^4，K最大可达N²，常规的全量排序、小顶堆取第K小的方法时间复杂度过高，无法满足性能要求，需要采用更高效的方案。

核心方案：二分答案 #

我们不需要生成所有网格元素，只要能快速统计出「小于等于某个值X的元素个数」，就可以通过二分X的取值范围，快速定位到第K小的元素，这是目前最优的实现思路。

步骤1：确定二分边界 #

• 左边界left：直接取网格最小元素，i、j从0开始的话取A[0][0]，从1开始的话取A[1][1]即可
• 右边界right：直接取网格最大元素，取A[N-1][N-1]（0下标）即可

步骤2：实现高效计数函数count(X) #

首先可以推导得出：任意一行的元素随j增大严格递增
证明：同一行i固定时，A[i][j+1] - A[i][j] = 2(i+j) + 1 + 10^5，该值恒大于0，所以每行元素都是严格递增的。
基于这个特性，对每一行用二分查找找到最大的j满足A[i][j] ≤ X，该行符合条件的元素个数就是j+1（0下标场景），累加所有行的结果就是总计数。
计数函数的时间复杂度为O(N log N)。

步骤3：二分查找定位第K小值 #

• 每次取中间值mid = (left + right) // 2
• 如果count(mid) ≥ K，说明第K小值小于等于mid，调整右边界right = mid
• 否则说明第K小值大于mid，调整左边界left = mid + 1
• 循环直到left == right，此时的值就是第K小元素

时间复杂度分析 #

网格元素最大值约为1.5*10^10，二分总次数约为35次，整体时间复杂度为O(35 * N log N)，N为5*10^4时单测试用例运算量约为2e7，完全满足性能要求。

注意事项 #

• 计算元素值时要使用64位整数，避免数值溢出
• 二分查找j时要注意边界不能超过N-1

内容的提问来源于stack exchange，提问作者tusharRawat