二维前缀异或和，1738. 找出第 K 大的异或坐标值

本文主要是介绍二维前缀异或和，1738. 找出第 K 大的异或坐标值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。

请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。

2、接口描述

python3

​

class Solution:def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:

cpp

​

class Solution {
public:int kthLargestValue(vector<vector<int>>& matrix, int k) {}
};

JS

/*** @param {number[][]} matrix* @param {number} k* @return {number}*/
var kthLargestValue = function(matrix, k) {};

3、原题链接

1738. 找出第 K 大的异或坐标值

---

二、解题报告

1、思路分析

计算二维前缀异或和，然后把所有值排序，取第k大即可

2、复杂度

时间复杂度： O(mnlog(mn))空间复杂度：O(mnlog(mn))

3、代码详解

python3

​

class Solution:def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:m, n = len(matrix), len(matrix[0])for i in range(1, m):matrix[i][0] ^= matrix[i - 1][0]for i in range(1, n):matrix[0][i] ^= matrix[0][i - 1]for i in range(1, m):for j in range(1, n):matrix[i][j] ^= (matrix[i - 1][j - 1] ^ matrix[i - 1][j] ^ matrix[i][j - 1])return sorted(x for row in matrix for x in row)[-k]

cpp

​

class Solution {
public:int kthLargestValue(vector<vector<int>>& matrix, int k) {int m = matrix.size(), n = matrix[0].size();vector<int> w;w.push_back(matrix[0][0]);for (int i = 1; i < m; i ++ ) w.push_back(matrix[i][0] ^= matrix[i - 1][0]);for (int i = 1; i < n; i ++ ) w.push_back(matrix[0][i] ^= matrix[0][i - 1]);for (int i = 1; i < m; i ++ ) for (int j = 1; j < n; j ++ ) w.push_back(matrix[i][j] ^= (matrix[i - 1][j] ^ matrix[i][j - 1] ^ matrix[i - 1][j - 1]));nth_element(w.begin(), w.end() - k, w.end());return w[w.size() - k];}
};

JS

/*** @param {number[][]} matrix* @param {number} k* @return {number}*/
var kthLargestValue = function(matrix, k) {const m = matrix.length, n = matrix[0].length;const w = [];w.push(matrix[0][0]);for (let i = 1; i < m; i ++ ) w.push(matrix[i][0] ^= matrix[i - 1][0]);for (let i = 1; i < n; i ++ ) w.push(matrix[0][i] ^= matrix[0][i - 1]);for (let i = 1; i < m; i ++ )for (let j = 1; j < n; j ++ )w.push(matrix[i][j] ^= (matrix[i - 1][j - 1] ^ matrix[i - 1][j] ^ matrix[i][j - 1]));w.sort((a, b) => b - a);return w[k - 1];
};

这篇关于二维前缀异或和，1738. 找出第 K 大的异或坐标值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---