[每日一题] 1738.找出第K大的异或坐标值

2024 年 05 月 26 日

99 次浏览

2396字数

> https://leetcode.cn/problems/find-kth-largest-xor-coordinate-value/description/?envType=daily-question&envId=2024-05-02

观察题目可知，二维数组中坐标 $(i, j)$ 的异或坐标值为 $(0, 0)$ 到 $(i, j)$ 的所有坐标值取异或。已知两个相同的数异或的结果为 0 ，而 0 和任意值异或都等于该值，所以坐标 $(i, j)$ 的异或坐标值可以通过 $(i - 1, j), (i, j - 1), (i - 1, j - 1)$ 三个坐标值进行异或运算得到。根据此方法可以递推出所有坐标的异或坐标值。

第 $k$ 个最大的异或坐标值，可以通过维护一个大小为 $k$ 的小顶堆得到。

```c++
class Solution {
public:
    int kthLargestValue(std::vector<std::vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();

std::priority_queue<int, std::vector<int>, std::greater<int>> res;
        for (int i = 1; i < m; i++)
            matrix[i][0] ^= matrix[i - 1][0];

for (int j = 1; j < n; j++)
            matrix[0][j] ^= matrix[0][j - 1];

for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                matrix[i][j] = matrix[i - 1][j] ^ matrix[i][j - 1] ^ matrix[i - 1][j - 1] ^ matrix[i][j];
    
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (res.size() < k) {
                    res.push(matrix[i][j]);
                } else if (matrix[i][j] > res.top()) {
                    res.pop();
                    res.push(matrix[i][j]);
                }
            }
        }

return res.top();
    }
};
```

- 时间复杂度：$O(mn \cdot log(k))$ 。计算所有异或坐标值需要 $O(mn)$ 的时间；每次更新堆需要 $O(logk)$ 时间，最坏情况下需要更新 $mn$ 次，因此最终时间复杂度为 $O(mn \cdot log(k))$ 。
- 空间复杂度：$O(mn)$ 。

找到第 $k$ 大元素的过程可以使用快排的思想进行优化，也就是快速选择算法：

```c++
class Solution {
public:
    int kthLargestValue(std::vector<std::vector<int>>& matrix, int k) {
        const int m = matrix.size(), n = matrix[0].size();

std::vector<int> res;
        res.resize(m * n);

for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i && j)
                    matrix[i][j] ^= matrix[i - 1][j - 1];
                if (i)
                    matrix[i][j] ^= matrix[i - 1][j];
                if (j)
                    matrix[i][j] ^= matrix[i][j - 1];
                res.push_back(matrix[i][j]);
            }
        }

nth_element(res.begin(), res.begin() + (k - 1) ,res.end(), std::greater<int>());

return res[k - 1];
    }
};
```

- 时间复杂度：$O(mn)$ 。计算所有异或坐标值的时间复杂度为 $O(mn)$，快速选择找出第 $k$ 大的元素的期望时间复杂度为 $O(mn)$ ，最坏情况下时间复杂度为 $O((mn)^2)$ ，因此总时间复杂度为 $O(mn)$ 。
- 空间复杂度：$O(mn)$，即为存储二维前缀和需要的空间。

最后修改：2024 年 05 月 26 日