本文主要是介绍Day 3:1738. 找出第 K 大的异或坐标值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Leetcode 1738. 找出第 K 大的异或坐标值
给你一个二维矩阵 matrix 和一个整数 k ,矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j](下标从 0 开始计数)执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值(k 的值从 1 开始计数)。
异或,用 ‘^’ 表示。
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 1
因此会存在 x ^ y ^x = y
其中异或坐标值表示的是:(a, b) 异或坐标值表示矩阵中从 (0, 0) 到 (a, b) 范围内所有元素的异或值。
用相同大小的数组保存 (a, b) 的异或值,则 (a, b) = (a, b - 1) ^ (a - 1, b) ^ (a - 1, b - 1) ^ matrix(a, b)。
(a, b - 1) ^ (a - 1, b) 计算两次 (a - 1, b - 1) 范围内的数据,因此再 ^ (a - 1, b - 1)。
用一个 List 保存每一点的值,最后使用 Collections.sort() 进行排序,注意,这个排序结果是升序。
完整代码
class Solution {public int kthLargestValue(int[][] matrix, int k) {List<Integer> list = new ArrayList<Integer>();int m = matrix.length;int n = matrix[0].length;int[][] tmp = new int[m][n];tmp[0][0] = matrix[0][0];list.add(tmp[0][0]);// 第一行for (int i = 1; i < n; i++) {tmp[0][i] = tmp[0][i - 1] ^ matrix[0][i];list.add(tmp[0][i]);}// 第一列for (int i = 1; i < m; i++) {tmp[i][0] = tmp[i - 1][0] ^ matrix[i][0];list.add(tmp[i][0]);}// 其他区域for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {tmp[i][j] = tmp[i][j - 1] ^ tmp[i - 1][j] ^ tmp[i- 1][j - 1]^ matrix[i][j];list.add(tmp[i][j]);}}Collections.sort(list);return list.get(list.size() - k);}
}
这篇关于Day 3:1738. 找出第 K 大的异或坐标值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!