综合笔试题：一道结合了「Top K + 前缀和」的数学题｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

题目描述

这是 LeetCode 上的 1738. 找出第 K 大的异或坐标值 ，难度为 中等。

Tag : 「Top K」、「数学」、「前缀和」

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

示例 1：

输入：matrix = [[5,2],[1,6]], k = 1

输出：7

解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
复制代码

示例 2：

输入：matrix = [[5,2],[1,6]], k = 2

输出：5

解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
复制代码

示例 3：

输入：matrix = [[5,2],[1,6]], k = 3

输出：4

解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
复制代码

示例 4：

输入：matrix = [[5,2],[1,6]], k = 4

输出：0

解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
复制代码

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 1000
• 0 <= matrix[i][j] <= $10^6$
• 1 <= k <= m * n

基本分析

根据题意，我们知道其实就是求「所有子矩阵中第 $k$ 大的异或和」，同时规定所有子矩阵的左上角端点为 $(0, 0)$。

数据范围为 $10^3$，因此「枚举所有右下角」并「每次计算子矩阵异或和」的朴素做法 $O(m^2 * n^2)$ 不用考虑。

要在全局中找最优，「枚举所有右下角」过程不可避免，我们可以优化「每次计算子矩阵异或和」的过程。

这个分析过程与 1310. 子数组异或查询 类似。

异或作为不进位加法，可以利用「偶数次异或结果为 $0$」的特性实现类似「前缀和」的容斥。这使得我们可以在 $O(1)$ 的复杂度内计算「某个子矩阵的异或和」。

二维前缀异或 & 优先队列（堆）

创建二维数组 $sum[][]$，令 $sum[i][j]$ 为以 $(i, j)$ 为右下角的子矩阵的异或和，我们可以得出计算公式：