本文正在參加「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 大的值。

解題思路

1. 維護一個前綴異或數組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();}

結果