Solution1 前缀和 + 最小堆
时间复杂度 O(m n logk)
空间复杂度 O(m * n)
我们可以建立一个大小为 k 的小根堆,在计算二维前缀异或时,判断当前「子矩阵异或和」是否大于堆顶元素:
大于堆顶元素:当前子矩阵异或和可能是第 k 大的值,堆顶元素不可能为第 k 大的值。将堆顶元素弹出,并将当前子矩阵和加入堆中 小于堆顶元素:不会是第 k 大的值,直接丢弃。 等于堆顶元素:有相同元素在堆中,直接丢弃。
最终的堆顶元素即为答案。
Previous1738_Find_Kth_Largest_XOR_Coordinate_ValueNext1744_Can_You_Eat_Your_Favorite_Candy_on_Your_Favorite_Day?
Last updated