leetcode每日一题
[1738] 找出第 K 大的异或坐标值
[1744] 你能在你最喜欢的那天吃到你最喜欢的糖果吗?
[231] 2的幂
堆排复习
[461] 汉明距离
[1190] 反转每对括号间的子串
[1707] 与数组中元素的最大异或值
[810] 黑板异或游戏
[1035] 不相交的线
[692] 前K个高频单词
[872] 叶子相似的树
[1442] 形成两个异或相等数组的三元组数目
[993] 二叉树的堂兄弟节点
[421] 数组中两个数的最大异或值
[13] 罗马数字转整数
[12] 整数转罗马数字
[1269]. 停在原地的方案数
[1310] 子数组异或查询
[1734] 解码异或后的排列
本文档使用 MrDoc 发布
-
+
首页
[1738] 找出第 K 大的异或坐标值
## [1738] 找出第 K 大的异或坐标值 [力扣原题链接](https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/) 给你一个二维矩阵 `matrix` 和一个整数 `k` ,矩阵大小为 `m x n` 由非负整数组成。 矩阵中坐标 `(a, b)` 的 **值** 可由对所有满足 `0 <= i <= a < m` 且 `0 <= j <= b < n` 的元素 `matrix[i][j]`(**下标从 0 开始计数** )执行异或运算得到。 请你找出 `matrix` 的所有坐标中第 `k` 大的值(**`k` 的值从 1 开始计数** )。 **示例 1:** <pre><strong> 输入:</strong>matrix = [[5,2],[1,6]], k = 1 <strong> 输出:</strong>7 <strong> 解释:</strong> 坐标 (0,1) 的值是 5 XOR 2 = 7 ,为最大的值。</pre> **示例 2:** <pre><strong> 输入:</strong>matrix = [[5,2],[1,6]], k = 2 <strong> 输出:</strong>5 <strong> 解释:</strong> 坐标 (0,0) 的值是 5 = 5 ,为第 2 大的值。</pre> **示例 3:** <pre><strong> 输入:</strong>matrix = [[5,2],[1,6]], k = 3 <strong> 输出:</strong>4 <strong> 解释:</strong> 坐标 (1,0) 的值是 5 XOR 1 = 4 ,为第 3 大的值。</pre> **示例 4:** <pre><strong> 输入:</strong>matrix = [[5,2],[1,6]], k = 4 <strong> 输出:</strong>0 <strong> 解释:</strong> 坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ,为第 4 大的值。</pre> **提示:** * `m == matrix.length` * `n == matrix[i].length` * `1 <= m, n <= 1000` * `0 <= matrix[i][j] <= 10<sup>6</sup>` * `1 <= k <= m * n` ### 题解 先计算每个坐标对应的值,再排序,获得第 K 大的值。计算每个坐标的值,可根据异或性质 a^b = c==>a^c = b 可得出: 依题意有:坐标(n,m)的值 =》 matrix[0][0] ^ matrix[0][1] ^ ... ^ matrix[0][m] ^ matrix[1][0] ^ ....^ matrix[n][m] ==> 坐标(n - 1, m) ^ 坐标(n,m - 1) ^ 坐标(n - 1,m - 1)^ matrix[n][m]. 其中 坐标(n - 1,m - 1)的目的是用于抵消 坐标(n - 1, m) ^ 坐标(n,m - 1)中计算了两遍的其中一遍数据。 ### 代码 ```cpp class Solution { public: int kthLargestValue(vector<vector<int>>& matrix, int k) { if(matrix.empty()) return 0; int height = (int)matrix.size(); int weight = (int)matrix[0].size(); vector<vector<int>> tmp_resurt(height + 1,vector<int>(weight + 1,0)); vector<int> nums_list; for(int i = 1; i < (int)tmp_resurt.size(); ++i) { for(int j = 1; j < (int)tmp_resurt[i].size(); ++j) { tmp_resurt[i][j] = tmp_resurt[i - 1][j] ^ tmp_resurt[i][j - 1] ^ matrix[i - 1][j - 1] ^ tmp_resurt[i - 1][j - 1]; nums_list.push_back(tmp_resurt[i][j]); } } std::sort(nums_list.begin(),nums_list.end(),greater<int>()); return nums_list[k - 1]; } }; ```
ty
2021年5月19日 14:01
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
阅读量
次
本站总访问量
次
本站访客数
人次
Markdown文件
分享
链接
类型
密码
更新密码