【LeetCode】找出第 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 开始计数)。
复制代码
思路
这是二维数组异或问题,解决异或问题,需要明确异或运算的基本性质。
异或运算的性质如下:
复制代码
在进行计算时,我们使用前缀和的方法提升解决问题的效率。前缀和是一种重要的预处理,能大大降低查询的时间复杂度。
AC 代码
复制代码
总结
上述代码的时间复杂度是 O(m * n * log (m * n)), 空间复杂度是 O(m * n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/986b59c90f544203feaf71a67】。文章转载请联系作者。
评论