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

# 题目

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

[https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/](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：**

```
输入：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 大的值。
```

# 题解

## 思路

动态规划获取前缀，再排序求k

## 代码

```javascript
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthLargestValue = function(matrix, k) {
    const m = matrix.length;
    const n = matrix[0].length;
    const dp = new Array(m + 1).fill(0).map(()=>new Array(n + 1).fill(0));
    // 保存结果
    const nums = [];
    for(let i = 1; i <= m; i++){
        for(let j = 1; j <= n; j++){
            dp[i][j] = dp[i - 1][j] ^ dp[i][j - 1] ^ dp[i - 1][j - 1] ^ matrix[i - 1][j - 1];
            nums.push(dp[i][j]);
        }
    }
    // 第 k 大元素的索引是 length - k
    return quickSort(nums, 0, nums.length - 1, nums.length - k);
};

/**
 * 快排
 * @param {Array} nums 数组
 * @param {int} left 
 * @param {int} right 
 * @param {int} target 
 * @returns 
 */
function quickSort(nums, left, right, target) {
    // 获取定位下标
    const index = randomPartition(nums, left, right);
    // 如果等于目标值，返回结果
    if(index === target){
        return nums[index];
    } else {
        return index > target ? quickSort(nums, left, index - 1, target) : quickSort(nums, index + 1, right, target) ;
    }
}

/**
 * 
 * @param {Array} nums 数组
 * @param {int} left 
 * @param {int} right  
 * @returns 
 */
function randomPartition(nums, left, right) {
    // 随机数 解决极端情况
    const index = Math.floor(Math.random() * (right - left + 1) + left);
    // 交换
    [nums[index], nums[left]] = [nums[left], nums[index]];
    return partition(nums, left, right);
}

/**
 * 划分元素
 * @param {Array} nums 数组
 * @param {int} left 
 * @param {int} right 
 * @returns 
 */
function partition(nums, left, right){
    // 锚点
    const pivot = nums[left];
    let j = left;
    for(let i = left + 1;i <= right; i++){
        // 小于锚点的放到左边，交换位置
        if(nums[i] < pivot){
            j++;
            // 交换
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }
    // 将锚点进行交换，该值就是当前最大的，左边都比它小，右边比它大
    [nums[left], nums[j]] = [nums[j], nums[left]];
    return j;
}
```

## 官方

```javascript
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 swap = (results, index1, index2) => {
    const temp = results[index1];
    results[index1] = results[index2];
    results[index2] = temp;
}
```