详解利用「二维前缀异或」&「优先队列(堆)」进行求解|Java 刷题打卡

简介: 详解利用「二维前缀异或」&「优先队列(堆)」进行求解|Java 刷题打卡

题目描述



这是 LeetCode 上的 1738. 找出第 K 大的异或坐标值 ,难度为 中等


Tag : 「Top 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] <= 10610^6106
  • 1 <= k <= m * n


基本分析



根据题意,我们知道其实就是求「所有子矩阵中第 kkk 大的异或和」,同时规定所有子矩阵的左上角端点为 (0,0)(0, 0)(0,0)


数据范围为 10310^3103,因此「枚举所有右下角」并「每次计算子矩阵异或和」的朴素做法 O(m2∗n2)O(m^2 * n^2)O(m2n2) 不用考虑。


要在全局中找最优,「枚举所有右下角」过程不可避免,我们可以优化「每次计算子矩阵异或和」的过程。


这个分析过程与 1310. 子数组异或查询 类似。


异或作为不进位加法,可以利用「偶数次异或结果为 000」的特性实现类似「前缀和」的容斥。这使得我们可以在 O(1)O(1)O(1) 的复杂度内计算「某个子矩阵的异或和」。


二维前缀异或 & 优先队列(堆)



创建二维数组 sum[][]sum[][]sum[][],令 sum[i][j]sum[i][j]sum[i][j] 为以 (i,j)(i, j)(i,j) 为右下角的子矩阵的异或和,我们可以得出计算公式:


sum[i][j]=sum[i−1][j]⊕sum[i][j−1]⊕sum[i−1][j−1]⊕matrix[i−1][j−1]sum[i][j] = sum[i - 1][j] ⊕ sum[i][j - 1] ⊕ sum[i - 1][j - 1] ⊕ matrix[i - 1][j - 1]sum[i][j]=sum[i1][j]sum[i][j1]sum[i1][j1]matrix[i1][j1]


剩下的问题是,如果从所有的「子矩阵异或和」找到第 kkk 大的值。


变成了 Top K 问题,可以使用「排序」或「堆」进行求解。


具体的,我们可以建立一个大小为 kkk 的小根堆,在计算二维前缀异或时,判断当前「子矩阵异或和」是否大于堆顶元素:


  • 大于堆顶元素:当前子矩阵异或和可能是第 kkk 大的值,堆顶元素不可能为第 kkk 大的值。将堆顶元素弹出,并将当前子矩阵和加入堆中
  • 小于堆顶元素:不会是第 kkk 大的值,直接丢弃。
  • 等于堆顶元素:有相同元素在堆中,直接丢弃。


最终的堆顶元素即为答案。


代码:


class Solution {
    public int kthLargestValue(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        PriorityQueue<Integer> q = new PriorityQueue<>(k, (a, b)->a - b);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] ^ sum[i][j - 1] ^ sum[i - 1][j - 1] ^ mat[i - 1][j - 1];
                if (q.size() < k) {
                    q.add(sum[i][j]);
                } else {
                    if (sum[i][j] > q.peek()) {
                        q.poll();
                        q.add(sum[i][j]);
                    }
                }
            }
        }
        return q.peek();
    }
}
复制代码


  • 时间复杂度:O(m∗n∗log⁡k)O(m * n * \log{k})O(mnlogk)
  • 空间复杂度:O(m∗n)O(m * n)O(mn)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.1738 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
【Java基础面试三十二】、new String(“abc“) 是去了哪里,仅仅是在堆里面吗?
这篇文章解释了Java中使用`new String("abc")`时,JVM会将字符串直接量"abc"存入常量池,并在堆内存中创建一个新的String对象,该对象会指向常量池中的字符串直接量。
|
存储 算法 Java
惊!Java程序员必看:JVM调优揭秘,堆溢出、栈溢出如何巧妙化解?
【8月更文挑战第29天】在Java领域,JVM是代码运行的基础,但需适当调优以发挥最佳性能。本文探讨了JVM中常见的堆溢出和栈溢出问题及其解决方法。堆溢出发生在堆空间不足时,可通过增加堆空间、优化代码及释放对象解决;栈溢出则因递归调用过深或线程过多引起,调整栈大小、优化算法和使用线程池可有效应对。通过合理配置和调优JVM,可确保Java应用稳定高效运行。
361 4
|
9月前
|
运维 监控 算法
企业局域网监控软件中 Java 优先队列算法的核心优势
企业局域网监控软件是数字化时代企业网络安全与高效运营的基石,犹如一位洞察秋毫的卫士。通过Java实现的优先队列算法,它能依据事件优先级排序,确保关键网络事件如异常流量、数据泄露等被优先处理,保障系统稳定与安全。代码示例展示了如何定义网络事件类并使用PriorityQueue处理高优先级事件,尤其在面对疑似风险时迅速启动应急措施。这一核心技术助力企业在复杂网络环境中稳健前行,护航业务腾飞。
121 32
|
存储 算法 Java
解释 Java 堆空间和垃圾收集
【8月更文挑战第22天】
95 0
|
9月前
|
监控 Java 中间件
8G的容器Java堆才4G怎么就OOM了?
本文记录最近一例Java应用OOM问题的排查过程,希望可以给遇到类似问题的同学提供参考。
|
11月前
|
安全 Java 编译器
Java对象一定分配在堆上吗?
本文探讨了Java对象的内存分配问题,重点介绍了JVM的逃逸分析技术及其优化策略。逃逸分析能判断对象是否会在作用域外被访问,从而决定对象是否需要分配到堆上。文章详细讲解了栈上分配、标量替换和同步消除三种优化策略,并通过示例代码说明了这些技术的应用场景。
204 4
Java对象一定分配在堆上吗?
|
10月前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
237 5
|
11月前
|
存储 Java 调度
Java 中的优先队列 PriorityQueue 详解
【10月更文挑战第22天】优先队列 PriorityQueue 是一种非常实用的数据结构,在许多场景中都能发挥重要作用。通过深入了解其特点和用法,我们可以更好地利用它来解决实际问题。
485 13
|
12月前
|
存储 算法 Java
🏗️Java零基础:深入了解Java 堆
【10月更文挑战第2天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
129 3
|
JSON 前端开发 JavaScript
java中post请求调用下载文件接口浏览器未弹窗而是返回一堆json,为啥
客户端调接口需要返回另存为弹窗,下载文件,但是遇到的问题是接口调用成功且不报错,浏览器F12查看居然返回一堆json,而没有另存为弹窗; > 正确的效果应该是:接口调用成功且浏览器F12不返回任何json,而是弹窗另存为窗口,直接保存文件即可。
454 2

热门文章

最新文章