問題

給你一個二維矩陣 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 大的值。

思想

前綴和+動態規劃，通過前面的異或值推理后面的異或值，最后進行排序找到第K大的值。

代碼

func kthLargestValue(matrix [][]int, k int) int {m,n := len(matrix),len(matrix[0])pre := make([][]int,m+1)res := make([]int,m*n)pre[0] = make([]int,n+1)for i, row := range matrix {pre[i+1] = make([]int,n+1)for j, val := range row {pre[i+1][j+1] = pre[i][j+1] ^ pre[i+1][j] ^ pre[i][j] ^ valres = append(res,pre[i+1][j+1])} }sort.Sort(sort.Reverse(sort.IntSlice(res)))return res[k-1]}