本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
位运算、状态压缩、枚举子集汇总

LeetCoce1738. 找出第 K 大的异或坐标值

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 目标值 可以通过对所有元素 matrix[i][j] 执行异或运算得到，其中 i 和 j 满足 0 <= i <= a < m 且 0 <= j <= b < n（下标从 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⁶
1 <= k <= m * n

前缀异或

preSum[i][j] 记录 前i行i列的异或和。
cur 记录nums[i…j]的异或值。
将所有异或值加到v中，直接用nth_element求第k大元素。不需要排序。
计算异或和 与求 k大，时间复杂度都是:O(nm)
空间复杂度也是：O(nm)

代码

核心代码

class Solution {
		public:
			int kthLargestValue(vector<vector<int>>& matrix, int k) {
				const int R = matrix.size();
				const int C = matrix.front().size();
				vector<vector<int>> preSum(R + 1, vector<int>(C + 1));
				vector<int> v;
				for (int r = 0; r < R; r++) {
					int cur = 0;
					for (int c = 0; c < C; c++) {
						cur ^= matrix[r][c];
						preSum[r + 1][c + 1] = preSum[r][c + 1] ^ cur;
						v.emplace_back(preSum[r + 1][c + 1]);
					}
				}
				nth_element(v.begin(), v.begin() + k - 1, v.end(), greater<>());
				return v[k - 1];
			}
		};

单元测试

vector<vector<int>> matrix;
		int k;
		TEST_METHOD(TestMethod11)
		{
			matrix = { {5,2},{1,6} }, k = 1;
			auto res = Solution().kthLargestValue(matrix, k);
			AssertEx(7, res);
		}
		TEST_METHOD(TestMethod12)
		{
			matrix = { {5,2},{1,6} }, k = 2;
			auto res = Solution().kthLargestValue(matrix, k);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod13)
		{
			matrix = { {5,2},{1,6} }, k = 3;
			auto res = Solution().kthLargestValue(matrix, k);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod14)
		{
			matrix = { {5,2},{1,6} }, k = 4;
			auto res = Solution().kthLargestValue(matrix, k);
			AssertEx(0, res);
		}