LeetCode——1738. 找出第 K 大的异或坐标值（Java）

题目简介

题干：
给你一个二维矩阵 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 大的值。

题解思路

返回第k个坐标中的异或值，因为二维数组的第几个元素首先想到排序算法

二维数组的排序算法用到Collections的sort方法，当然我们得先获取结果数组

因为结果数组的每个位置的元素都是以前元素疑惑的结果，所以这里可以说是前缀和的思想

正确代码

    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> result = new ArrayList<>();

        //根据公式计算每个位置的异或值保存到新数组中
        //这里要注意下标从1开始
        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];
                result.add(pre[i][j]);
            }
        }
        //对结果数组进行排序
        Collections.sort(result, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 -o1;
            }
        });
        return result.get(k - 1);
    }

总结

前缀和的思路不仅仅用于搜索提示等方向，只要是涉及后者依靠前者都可以采用这种思路

当然给出的代码只是较为简单的思路，你当然可以先一维前缀和，然后再计算二维前缀和

或者在最后找到第k个的时候不采用排序的方式，其他方法请看官方评论区大佬们的答案

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见！

LeetCode——1738. 找出第 K 大的异或坐标值（Java）

原文：https://www.cnblogs.com/bc-song/p/14783752.html