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

Leetcode-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 开始计数）。

• 注意：^ 表示 按位异或 操作

前言

• 因此我们可以使用「前缀和」这一技巧对按位异或运算的结果进行维护。由于本题中给定的矩阵matrix 是二维的，因此我们需要使用二维前缀和。
• 二位前缀和 pre(i,j) = pre(i - 1,j) ^ pre(i , j - 1) ^ pre(i - 1,j - 1) ^ matrix(i,j)

• 下图给出了该二维前缀和递推式的可视化展示。

• 因为当我们 pre(i - 1,j)， pre(i , j - 1) 进行按位异或运算后，由于对一个数异或等于本身x⊕y⊕y=x
• 因此pre(i - 1, j - 1) 对应区域的异或结果被抵消，我们需要将其补上，对位置 (i, j）的元素进行按位异或运算，这样就得到了 pre(i,j)。

方法一 ： 排序 + 二维前缀和

• 在得到了所有的二维前缀和之后，我们只需要找出其中第 k 大的元素即为答案。
• 这一步我们可以直接将mn个二维前缀和进行排序后返第 k 大的元素，也可以参考「215. 数组中的第 K 个最大元素的官方题解」中时间复杂度更低的做法。

细节：

• 在二维前缀和的计算过程中，如果我们正在计算首行或者首列，即 i=0或 j=0
• 此时pre(i - 1, j - 1) 的下标越界，因此我们可以使用一个(m + 1) * （n + 1）大小的二维矩阵，首行和首列空出来赋予默认值 0
• 并使用接下来的 m行和 n 列存储二维前缀和，这样就不必进行下标范围的判断了。

class Solution {
    public int kthLargestValue(int[][] matrix, int k) {
        // 1. 构造二维前缀和
        int m = matrix.length;
        int 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]);
            }
        }

        // 2. 对前缀和进行排序 : 降序排序
        Collections.sort(results,new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });

        // 3. 返回第k大
        return results.get(k - 1);
    }
}

复杂度分析

• 时间复杂度：O(mnlog(mn))。计算二维前缀和的时间复杂度为O(mn)，排序的时间复杂度为O(mnlog(mn))，因此总时间复杂度为 O(mnlog(mn))。

• 空间复杂度：O(mn)，即为存储二维前缀和需要的空间。

打赏