This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

You are given a two dimensional matrix matrix and an integer k of size m, x and n consisting of non-negative integers.

The values of the coordinates (a, b) in the matrix can be obtained by performing xOR on all elements of matrix[I][j] (counting subscripts from 0) such that 0 <= I <= a < m and 0 <= j <= b < n.

Please find the KTH largest value of all the coordinates of the matrix (the value of k is counted from 1).

  • Example 1:

Input: matrix = [[5,2],[1,6]], k = 1 output: 7 interpretation: the value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

  • Example 2:

Input: matrix = [[5,2],[1,6]], k = 2 output: 5 interpretation: the value of coordinate (0,0) is 5 = 5, which is the second largest value.

  • Example 3:

Input: matrix = [[5,2],[1,6]], k = 3 Output: 4 Interpretation: the value of the coordinate (1,0) is 5 XOR 1 = 4, which is the third largest value.

  • Example 4:

Input: matrix = [[5,2],[1,6]], k = 4 Output: 0 Interpretation: the value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the fourth largest value.

Their thinking

  1. Maintain a prefix exclusive or array sum [I] [j], on behalf of (I, j) as exclusive or result of the lower right corner rectangle, so the sum [I] [j] values can be from sum [j], [I – 1] sum [I] [1], the sum] [I – 1 in the result of [1] and recursion formula forsum[i][j]=sum[i-1][j]^sum[i][j-1]^sum[i-1][j-1]^matrix[i-1][j-1];

2. Sort all xor arrays once to get the KTH largest element

code

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);
        returnlist.get(list.size()-k); }}Copy the code

The results of

Use priority queues for sorting

    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();

    }
Copy the code

The results of