本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述

二、解题思路

1.暴力枚举

暴力枚举总能解决问题。先计算每个坐标得异或值再排序找k大异或坐标值。

时间复杂度分析

• 计算异或值：O((1+mn)nm/2)=O((mn)^2)
• 排序（快排）：O(mnlogmn)

空间复杂度分析

• 需要nm个空间存储异或值：O(mn)

2.优化异或值计算-前缀和

我们发现计算异或值是瓶颈，如何优化呢？
我们发现暴力枚举每次都重复计算两个数的异或，我们能否记录这些历史值呢？
答案是可以的。
异或运算满足交换律：

a⊕b=b⊕a
复制代码

以及结合律：

(a⊕b)⊕c=a⊕(b⊕c)
复制代码

还有一个性质2个相同数异或会相互抵消：

x⊕y⊕y=x
复制代码

根据已上性质我们可以得到前缀和计算公式：

pre(i,j)=pre(i−1,j)⊕pre(i,j−1)⊕pre(i−1,j−1)⊕matrix(i,j)
复制代码

时间复杂度分析

• 计算异或值：O(mn)
• 排序（快排）：O(mnlogmn)

空间复杂度分析

• 需要nm个空间存储异或值：O(mn)

3.优化k大选择-快速选择算法

我们发现排序成了算法瓶颈，如何优化呢？
寻找k大值，是否想到了经典题目（215. 数组中的第 K 个最大元素）？
是的，我们可以用快排在排序中找到k大值。
具体细节下篇文章分析。

时间复杂度分析

• 计算异或值：O(mn)
• 快速选择（快排）：平均O(mn)

空间复杂度分析

• 需要nm个空间存储异或值：O(mn)

三、代码实现

class Solution {
    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> 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]);
            }
        }

        nthElement(results, 0, k - 1, results.size() - 1);
        return results.get(k - 1);
    }

    public void nthNum(List<Integer> results, int left, int kth, int right) {
        if (left == right) {
            return;
        }
        int pivot = (int) (left + Math.random() * (right - left + 1));
        swap(results, pivot, right);
        int sepl = left - 1, sepr = left - 1;
        for (int i = left; i <= right; i++) {
            if (results.get(i) > results.get(right)) {
                swap(results, ++sepr, i);
                swap(results, ++sepl, sepr);
            } else if (results.get(i) == results.get(right)) {
                swap(results, ++sepr, i);
            }
        }
        if (sepl < left + kth && left + kth <= sepr) {
            return;
        } else if (left + kth <= sepl) {
            nthNum(results, left, kth, sepl);
        } else {
            nthNum(results, sepr + 1, kth - (sepr - left + 1), right);
        }
    }

    public void swap(List<Integer> results, int index1, int index2) {
        int temp = results.get(index1);
        results.set(index1, results.get(index2));
        results.set(index2, temp);
    }
}
复制代码