Medium

题目描述

给你一个二维矩阵 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 大值。

提示：

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

解题思路

这道题需要计算每个坐标位置的异或值，然后找出第k大的值。关键是理解坐标 (a, b) 的值是从 (0,0) 到 (a,b) 构成的矩形区域内所有元素的异或结果。

解题思路：

  1. 二维前缀异或和：类似于二维前缀和，我们可以构建二维前缀异或数组。对于位置 (i,j)，前缀异或值为从 (0,0) 到 (i,j) 的所有元素异或结果。

  2. 递推公式：prefix[i][j] = matrix[i][j] XOR prefix[i-1][j] XOR prefix[i][j-1] XOR prefix[i-1][j-1]

    • 这是因为 prefix[i-1][j-1] 在前两项中被异或了两次，需要再异或一次来消除（异或的性质：a XOR a = 0）

  3. 收集所有值并排序：将所有前缀异或值收集到数组中，排序后返回第k大的值。

优化方案：

  • 可以使用快速选择算法（Quickselect）来优化找第k大元素的过程，时间复杂度可以达到平均 O(mn)
  • 也可以使用最小堆维护k个最大值，空间复杂度更优

本解法采用排序方法，思路清晰易懂。

代码实现

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));
        vector<int> values;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i][j] = matrix[i-1][j-1] ^ prefix[i-1][j] ^ prefix[i][j-1] ^ prefix[i-1][j-1];
                values.push_back(prefix[i][j]);
            }
        }
        
        sort(values.begin(), values.end(), greater<int>());
        return values[k-1];
    }
};

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        prefix = [[0] * (n + 1) for _ in range(m + 1)]
        values = []
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = matrix[i-1][j-1] ^ prefix[i-1][j] ^ prefix[i][j-1] ^ prefix[i-1][j-1]
                values.append(prefix[i][j])
        
        values.sort(reverse=True)
        return values[k-1]

public class Solution {
    public int KthLargestValue(int[][] matrix, int k) {
        int m = matrix.Length, n = matrix[0].Length;
        int[,] prefix = new int[m + 1, n + 1];
        List<int> values = new List<int>();
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefix[i, j] = matrix[i-1][j-1] ^ prefix[i-1, j] ^ prefix[i, j-1] ^ prefix[i-1, j-1];
                values.Add(prefix[i, j]);
            }
        }
        
        values.Sort((a, b) => b.CompareTo(a));
        return values[k-1];
    }
}

var kthLargestValue = function(matrix, k) {
    const m = matrix.length, n = matrix[0].length;
    const prefix = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    const values = [];
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            prefix[i][j] = matrix[i-1][j-1] ^ prefix[i-1][j] ^ prefix[i][j-1] ^ prefix[i-1][j-1];
            values.push(prefix[i][j]);
        }
    }
    
    values.sort((a, b) => b - a);
    return values[k-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn + mn log(mn))构建前缀异或数组需要O(mn)，排序需要O(mn log(mn))
空间复杂度O(mn)前缀数组和values数组各需要O(mn)空间