【Day23】1738.找出第 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.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 <= matrix[i][j] <= 106
  • 1 <= k <= m * n

题解:

二维差分+最小堆

前缀和模板+维护k个元素的最小堆

class Solution {
public:
    int prefix[1000][1000];
    int kthLargestValue(vector>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefix[0][0] = matrix[0][0];
        // 处理第一行
        for (int i = 1; i < n; i++) {
            prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
        }
        // 处理第一列
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
            }
        }

        priority_queue, std::greater> pq;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                pq.push(prefix[i][j]);
                if (pq.size() > k) pq.pop();
            }
        }
        return pq.top();
    }
};

二分搜值

每次猜测一个值x,然后遍历前缀和矩阵,统计有多少个元素大于等于x,如果count小于k,那么x肯定不可能是答案,我们将猜测的上界下调至x-1;否则,我们就将猜测的下界调整至x。可以看到问题可以转换为查找最后一个小于等于target的数。因为当查找到大于等于target时要往上不断压缩区间,直到小于等于k为止。

class Solution {
public:
    int prefix[1000][1000];
    int m, n;
    int kthLargestValue(vector>& matrix, int k) {
        m = matrix.size();
        n = matrix[0].size();
        prefix[0][0] = matrix[0][0];
        // 处理第一行
        for (int i = 1; i < n; i++) {
            prefix[0][i] = prefix[0][i - 1] ^ matrix[0][i];
        }
        // 处理第一列
        for (int i = 1; i < m; i++) {
            prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ matrix[i][j] ^ prefix[i - 1][j - 1];
            }
        }

        int left = 0, right = 1e6;
        while (left < right) {
            int mid = right - (right - left - 1) / 2;
            if (count(mid) < k) { // 缩小值
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
    int count (int mid) {
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (prefix[i][j] >= mid) cnt++;
            }
        }
        return cnt;
    }
};

   转载规则


《【Day23】1738.找出第 K 大的异或坐标值》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day24】692.前K个高频单词 【Day24】692.前K个高频单词
692. 前K个高频单词给一非空的单词列表,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。 示例 1: 输入: ["i", "lov
2021-05-20
下一篇 
【Day22】1442.形成两个异或相等数组的三元组数目 【Day22】1442.形成两个异或相等数组的三元组数目
1442. 形成两个异或相等数组的三元组数目 给你一个整数数组 arr 。 现需要从数组中取三个下标 i、j 和 k ,其中 (0 <= i < j <= k < arr.length) 。 a 和 b 定义如下:
2021-05-18
  目录