【leetcode 找出第 K 大的异或坐标值]

前缀和 + 最小堆

import java.util.PriorityQueue;

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.kthLargestValue(new int[][]{
                {5, 2}, {1, 6}
        }, 4);
    }

    public int kthLargestValue(int[][] matrix, int k) {
        int m = matrix.length;
        int n = matrix[0].length;

        // row
        int[][] rowXor = new int[m][n];
        for (int i = 0; i < m; i++) {
            rowXor[i][0] = matrix[i][0];
            for (int j = 1; j < n; j++) {
                rowXor[i][j] = rowXor[i][j - 1] ^ matrix[i][j];
            }
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k) {
            @Override
            public boolean add(Integer value) {
                if (size() < k) {
                    return super.add(value);
                } else {
                    int kThNum = peek();
                    if (kThNum < value) {
                        poll();
                        super.add(value);
                    }
                    return true;
                }
            }
        };

        int[][] transform = new int[m][n];
        int value = matrix[0][0];
        transform[0][0] = value;
        priorityQueue.add(value);
        for (int col = 1; col < n; col++) {
            transform[0][col] = transform[0][col - 1] ^ matrix[0][col];
            priorityQueue.add(transform[0][col]);
        }
        for (int row = 1; row < m; row++) {
            for (int col = 0; col < n; col++) {
                transform[row][col] = transform[row - 1][col] ^ rowXor[row][col];
                priorityQueue.add(transform[row][col]);
            }
        }
        return priorityQueue.peek();
    }
}