文章目錄

• • 1. 題目
  • 2. 解題

947 / 3851，前 24.6%

2533 / 11282，前 22.5%

1. 題目

給你一個二維矩陣 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 大的值。提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 1000 0 <= matrix[i][j] <= 10^6 1 <= k <= m * n

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 取第K大的值，偷懶直接排序做，時間復雜度 $O(mn\log (mn))$
• 也可以使用容量為 k 的小頂堆做，時間復雜度 $O(mn\log (k))$
• 可以使用快排做法，時間復雜度 $O(mn)$

class Solution { public:int kthLargestValue(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));vector<int> ans(m*n);int K = 0;for(int i = 1; i <= m; i++) {for(int j = 1; j <= n; j++) {// 方便代碼處理邊界，下標從1開始dp[i][j] = dp[i-1][j]^dp[i][j-1]^dp[i-1][j-1]^mat[i-1][j-1];ans[K++] = dp[i][j];}}sort(ans.begin(), ans.end());return ans[m*n-k];} };

500 ms 110.8 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1738. 找出第 K 大的异或坐标值（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。