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

参考1738. 找出第 K 大的异或坐标值，难度分1671。

题目

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。矩阵中坐标 (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,1) 的值是 5 XOR 2 = 7 ，为最大的值。
输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。

解题思路

• 动态规划+排序：使用动态规划快速计算出所有坐标值,也可用前缀和,然脏排序后返回第n-k个元素。
• 动态规划+快速选择：动态规划计算出坐标值后,进行快速选择算法。

动态规划+排序

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        //先动态规划计算所有坐标值
        int[][] values = new int[m][n];
        int[] cols = new int[n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                cols[j] ^= matrix[i][j]; //记录j列的坐标值
                if(j == 0) values[i][j] = cols[j];
                else values[i][j] = values[i][j-1] ^ cols[j];
            }
        }
        int[] res = new int[m*n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) res[i*n+j] = values[i][j];
        }
        //考虑对所有值排序
        Arrays.sort(res);
        return res[m*n-k];
    }
}

复杂度分析

• 时间复杂度：O(mnlogmn),m/n分别为矩阵行/列数,动态规划为O(mn),排序为O(mnlogmn)。
• 空间复杂度：O(mn),主要为动态规划空间。

动态规划+快速选择

class Solution {
    int[] res;
    int k;
    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        //先动态规划计算所有坐标值
        int[][] values = new int[m][n];
        int[] cols = new int[n];
        res = new int[m*n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                cols[j] ^= matrix[i][j]; //记录j列的坐标值
                if(j == 0) res[i*n+j] = cols[j];
                else res[i*n+j] = res[i*n+j-1] ^ cols[j];
            }
        }
        // for(int i = 0; i < m; i++) {
        //     for(int j = 0; j < n; j++) res[i*n+j] = values[i][j];
        // }
        //考虑快速选择
        // int left = 0,right = res.length-1;
        // while(true) {
        //     int index = quickSelect(left,right);
        //     if(index == k-1) return res[index];
        //     else if(index < k-1) left = index+1;
        //     else right = index-1;
        // }
        this.k = k;
        return quickSelect(0,res.length-1);
    }

    Random random = new Random();
    int quickSelect(int start,int end) {
        int pos = start + random.nextInt(end-start+1);
        int base = res[pos];
        swap(start,pos);
        int index = start;
        for(int i = start+1; i <= end; i++) {
            if(res[i] > base && ++index != i) swap(i,index);
        }
        swap(start,index);
        if(index == k-1) return res[index];
        else if(index < k-1) return quickSelect(index+1,end);
        return quickSelect(start,index-1);
    }
    void swap(int x,int y) {
        int tmpx = res[x];
        res[x] = res[y];
        res[y] = tmpx;
    }
}

复杂度分析

• 时间复杂度：O(mn),动态规划遍历和快速选择都为O(mn)。
• 空间复杂度：O(mn),主要为动态规划空间。