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

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

题目

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

解题思路

维护一个前缀异或数组sum[i][j],代表以（i，j）为右下角的矩形的异或结果，因此sum[i][j]的值可以从sum[i-1][j]，sum[i][j-1]，sum[i-1][j-1]的结果中推出来，递推式为sum[i][j]=sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];

2. 将所有异或的数组进行一次排序，就能得出第k大的元素了

代码

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {

        ArrayList<Integer> list = new ArrayList<>();
        int n=matrix.length,m=matrix[0].length,res=0;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j]=sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];
                list.add(sum[i][j]);
            }
        }
        Collections.sort(list);
        return list.get(list.size()-k);
        
    }
}
复制代码

结果

使用优先队列进行排序

    public int kthLargestValue(int[][] matrix, int k) {

        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
        int n=matrix.length,m=matrix[0].length,res=0;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j]=sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];
                if(priorityQueue.size()<k)
                {
                    priorityQueue.add(sum[i][j]);
                }else if(priorityQueue.peek()<sum[i][j])
                {
                    priorityQueue.poll();
                    priorityQueue.add(sum[i][j]);
                }
            }
        }

        return priorityQueue.peek();

    }
复制代码