Solution1 前缀和 + 最小堆

  • 时间复杂度 O(m n logk)

  • 空间复杂度 O(m * n)

我们可以建立一个大小为 k 的小根堆,在计算二维前缀异或时,判断当前「子矩阵异或和」是否大于堆顶元素:

大于堆顶元素:当前子矩阵异或和可能是第 k 大的值,堆顶元素不可能为第 k 大的值。将堆顶元素弹出,并将当前子矩阵和加入堆中 小于堆顶元素:不会是第 k 大的值,直接丢弃。 等于堆顶元素:有相同元素在堆中,直接丢弃。

最终的堆顶元素即为答案。

Last updated