第 225 场周赛 5663. 找出第 K 大的异或坐标值

Desciption

给你一个 n * m 矩阵 matrix 和一个整数 k ， 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）

示例：

输入: matrix = [[5,2],[1,6]], k = 1
输出: 7
解释：坐标 (0,0) 的值是 5 = 5，(0,1) 的值是 5 XOR 2 = 7，(1,0) 的值是 5 XOR 1 = 4，坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0，所以最大的值是 7

Solution

  1. 理清楚题意后，可以知道坐标 (x, y) 的值实际上就是在 左上角所有 matrix[i][j] 的异或值
  2. 处理 行和列的异或前缀和，用 f 和 h 数组表示。则可以用 dp 来得到结果数组：res[i][j] = res[i-1][j-1] ^ f[i][j] ^ h[i-1][j]; 。然后排序得到第 k 大

Code

    public static int kthLargestValue(int[][] matrix, int k) {
        int n = matrix.length;
        if (n <= 0) {
            return 0;
        }
        int m = matrix[0].length;

        int[][] res = new int[n+1][], f = new int[n+1][], h = new int[n+1][];
        for (int i = 0; i <= n; ++i) {
            res[i] = new int[m+1];
            f[i] = new int[m+1];
            h[i] = new int[m+1];
            Arrays.fill(res[i], 0);
            Arrays.fill(f[i], 0);
            Arrays.fill(h[i], 0);
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                f[i][j] = f[i][j-1] ^ matrix[i-1][j-1];
                h[i][j] = h[i-1][j] ^ matrix[i-1][j-1];
            }
        }

        int[] ans = new int[n*m];
        int count = 0;
        for (int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                res[i][j] = res[i-1][j-1] ^ f[i][j] ^ h[i-1][j];
                ans[count] = res[i][j];
                count++;
            }
        }

        Arrays.sort(ans);
        return ans[n*m-k];
    }