class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
}
};
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 开始计数）。
示例 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.lengthn == matrix[i].length1 <= m, n <= 10000 <= matrix[i][j] <= 1061 <= k <= m * n原站题解
java 解法, 执行用时: 152 ms, 内存消耗: 180.3 MB, 提交时间: 2024-05-26 00:08:35
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int[][] pre = new int[m + 1][n + 1];
List<Integer> results = new ArrayList<Integer>();
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.add(pre[i][j]);
}
}
nthElement(results, 0, k - 1, results.size() - 1);
return results.get(k - 1);
}
public void nthElement(List<Integer> results, int left, int kth, int right) {
if (left == right) {
return;
}
int pivot = (int) (left + Math.random() * (right - left + 1));
swap(results, pivot, right);
// 三路划分（three-way partition）
int sepl = left - 1, sepr = left - 1;
for (int i = left; i <= right; i++) {
if (results.get(i) > results.get(right)) {
swap(results, ++sepr, i);
swap(results, ++sepl, sepr);
} else if (results.get(i) == results.get(right)) {
swap(results, ++sepr, i);
}
}
if (sepl < left + kth && left + kth <= sepr) {
return;
} else if (left + kth <= sepl) {
nthElement(results, left, kth, sepl);
} else {
nthElement(results, sepr + 1, kth - (sepr - left + 1), right);
}
}
public void swap(List<Integer> results, int index1, int index2) {
int temp = results.get(index1);
results.set(index1, results.get(index2));
results.set(index2, temp);
}
}
cpp 解法, 执行用时: 250 ms, 内存消耗: 126 MB, 提交时间: 2024-05-26 00:08:08
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
vector<int> results;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.push_back(pre[i][j]);
}
}
nth_element(results.begin(), results.begin() + k - 1, results.end(), greater<int>());
return results[k - 1];
}
};
cpp 解法, 执行用时: 306 ms, 内存消耗: 126.9 MB, 提交时间: 2024-05-26 00:07:49
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> pre(m + 1, vector<int>(n + 1));
vector<int> results;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.push_back(pre[i][j]);
}
}
sort(results.begin(), results.end(), greater<int>());
return results[k - 1];
}
};
javascript 解法, 执行用时: 188 ms, 内存消耗: 109.2 MB, 提交时间: 2022-11-27 12:47:38
/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
var kthLargestValue = function(matrix, k) {
const m = matrix.length, n = matrix[0].length;
const pre = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
const results = [];
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.push(pre[i][j]);
}
}
nthElement(results, 0, k - 1, results.length - 1);
return results[k - 1];
}
const nthElement = (results, left, kth, right) => {
if (left === right) {
return;
}
const pivot = parseInt(Math.random() * (right - left) + left);
swap(results, pivot, right);
// 三路划分（three-way partition）
let sepl = left - 1, sepr = left - 1;
for (let i = left; i <= right; i++) {
if (results[i] > results[right]) {
swap(results, ++sepr, i);
swap(results, ++sepl, sepr);
} else if (results[i] === results[right]) {
swap(results, ++sepr, i);
}
}
if (sepl < left + kth && left + kth <= sepr) {
return;
} else if (left + kth <= sepl) {
nthElement(results, left, kth, sepl);
} else {
nthElement(results, sepr + 1, kth - (sepr - left + 1), right);
}
}
const swap = (results, index1, index2) => {
const temp = results[index1];
results[index1] = results[index2];
results[index2] = temp;
}
golang 解法, 执行用时: 312 ms, 内存消耗: 34.8 MB, 提交时间: 2022-11-27 12:47:10
func quickSelect(a []int, k int) int {
rand.Shuffle(len(a), func(i, j int) { a[i], a[j] = a[j], a[i] })
for l, r := 0, len(a)-1; l < r; {
v := a[l]
i, j := l, r+1
for {
for i++; i < r && a[i] < v; i++ {
}
for j--; j > l && a[j] > v; j-- {
}
if i >= j {
break
}
a[i], a[j] = a[j], a[i]
}
a[l], a[j] = a[j], v
if j == k {
break
} else if j < k {
l = j + 1
} else {
r = j - 1
}
}
return a[k]
}
func kthLargestValue(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
results := make([]int, 0, m*n)
pre := make([][]int, m+1)
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+1][j] ^ pre[i][j+1] ^ pre[i][j] ^ val
results = append(results, pre[i+1][j+1])
}
}
return quickSelect(results, m*n-k)
}
python3 解法, 执行用时: 1596 ms, 内存消耗: 45.6 MB, 提交时间: 2022-11-27 12:46:53
class Solution:
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
m, n = len(matrix), len(matrix[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
results = list()
for i in range(1, m + 1):
for j in range(1, n + 1):
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]
results.append(pre[i][j])
def nth_element(left: int, kth: int, right: int, op: Callable[[int, int], bool]):
if left == right:
return
pivot = random.randint(left, right)
results[pivot], results[right] = results[right], results[pivot]
# 三路划分（three-way partition）
sepl = sepr = left - 1
for i in range(left, right + 1):
if op(results[i], results[right]):
sepr += 1
if sepr != i:
results[sepr], results[i] = results[i], results[sepr]
sepl += 1
if sepl != sepr:
results[sepl], results[sepr] = results[sepr], results[sepl]
elif results[i] == results[right]:
sepr += 1
if sepr != i:
results[sepr], results[i] = results[i], results[sepr]
if sepl < left + kth <= sepr:
return
elif left + kth <= sepl:
nth_element(left, kth, sepl, op)
else:
nth_element(sepr + 1, kth - (sepr - left + 1), right, op)
nth_element(0, k - 1, len(results) - 1, operator.gt)
return results[k - 1]
javascript 解法, 执行用时: 624 ms, 内存消耗: 105.2 MB, 提交时间: 2022-11-27 12:46:27
/**
* @param {number[][]} matrix
* @param {number} k
* @return {number}
*/
var kthLargestValue = function(matrix, k) {
const m = matrix.length, n = matrix[0].length;
const pre = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
const results = [];
for (let i = 1; i < m + 1; i++) {
for (let j = 1; j < n + 1; j++) {
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1];
results.push(pre[i][j]);
}
}
results.sort((a, b) => b - a);
return results[k - 1];
}
golang 解法, 执行用时: 448 ms, 内存消耗: 34.3 MB, 提交时间: 2022-11-27 12:46:09
func kthLargestValue(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
results := make([]int, 0, m*n)
pre := make([][]int, m+1)
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+1][j] ^ pre[i][j+1] ^ pre[i][j] ^ val
results = append(results, pre[i+1][j+1])
}
}
sort.Sort(sort.Reverse(sort.IntSlice(results)))
return results[k-1]
}
python3 解法, 执行用时: 1068 ms, 内存消耗: 43.7 MB, 提交时间: 2022-11-27 12:45:55
class Solution:
def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
m, n = len(matrix), len(matrix[0])
pre = [[0] * (n + 1) for _ in range(m + 1)]
results = list()
for i in range(1, m + 1):
for j in range(1, n + 1):
pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]
results.append(pre[i][j])
results.sort(reverse=True)
return results[k - 1]