V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Leviathann
V2EX  ›  程序员

leetcode 240 二维二分查找的解法速度好像还不如直接左下或者右上线性查找的解法 kotlin 时间 43% 内存 22%

  •  
  •   Leviathann · 2021-05-16 06:01:00 +08:00 · 1400 次点击
    这是一个创建于 1047 天前的主题,其中的信息可能已经有所发展或是发生改变。

    而且代码量多了好多倍,二维矩阵的对角线上二分查找那边界条件 debug 了半天才写对
    思路是在对角线上找到 a < target < b 的相邻值 a 和 b,a 的左上角所有元素都小于 target,b 的右下角所有元素都大于 target,然后递归的在右上和左下找

    实际就是官方解法 3 的拓展提到的解法,翻了下题解区好像都没找到实现了这种解法的
    我一开始的思路就是这个,写到一半感觉太麻烦就想翻答案看看是不是想错了,结果发现官方也只把这个作为拓展

    class Solution {
    
        fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
            if (matrix.isEmpty() || matrix[0].isEmpty()) {
                return false
            }
            return searchSubMatrix(matrix, target, 0, matrix[0].size - 1, 0, matrix.size - 1)
        }
    
        private fun searchSubMatrix(
            matrix: Array<IntArray>,
            target: Int,
            xmin: Int,
            xmax: Int,
            ymin: Int,
            ymax: Int
        ): Boolean {
            if (xmin == xmax && ymin == ymax) {
                return retrieveValAtPos(matrix, Pair(xmin, ymin)) == target
            }
            val (upLeftBound, downRightBound) = findRange(matrix, target, xmin, xmax, ymin, ymax) ?: return true
            return searchSubMatrix(
                matrix,
                target,
                if (upLeftBound.first + 1 > xmax) xmax else upLeftBound.first + 1,
                xmax,
                ymin,
                if (downRightBound.second - 1 < ymin) ymin else downRightBound.second - 1
            ) || searchSubMatrix(
                matrix,
                target,
                xmin,
                if (downRightBound.first - 1 < xmin) xmin else downRightBound.first - 1,
                if (upLeftBound.second + 1 > ymax) ymax else upLeftBound.second + 1,
                ymax,
            )
        }
    
        private fun retrieveValAtPos(matrix: Array<IntArray>, pos: Pair<Int, Int>): Int {
            return matrix[pos.second][pos.first]
        }
    
        private fun findRange(
            matrix: Array<IntArray>,
            target: Int,
            xmin: Int,
            xmax: Int,
            ymin: Int,
            ymax: Int
        ): Pair<Pair<Int, Int>, Pair<Int, Int>>? {
            var lower = Pair(xmin, ymin)
            var upper = Pair(xmax, ymax)
            var center: Pair<Int, Int>
            var centerVal: Int
            while (lower.first < upper.first || lower.second < upper.second) {
                center = Pair(
                    lower.first + (upper.first - lower.first) / 2,
                    lower.second + (upper.second - lower.second) / 2
                )
                centerVal = retrieveValAtPos(matrix, center)
                when {
                    centerVal > target -> {
                        upper = Pair(
                            if (upper.first == xmin) xmin else upper.first - 1,
                            if (upper.second == ymin) ymin else upper.second - 1
                        )
                    }
                    centerVal < target -> {
                        lower = Pair(
                            if (lower.first == xmax) xmax else lower.first + 1,
                            if (lower.second == ymax) ymax else lower.second + 1
                        )
                    }
                    else -> {
                        return null
                    }
                }
            }
            when {
                retrieveValAtPos(matrix, lower) > target -> {
                    return Pair(
                        Pair(
                            if (upper.first == xmin) xmin else upper.first - 1,
                            if (upper.second == ymin) ymin else upper.second - 1
                        ),
                        lower
                    )
                }
                retrieveValAtPos(matrix, lower) < target -> {
                    return Pair(
                        lower,
                        Pair(
                            if (lower.first == xmax) xmax else lower.first + 1,
                            if (lower.second == ymax) ymax else lower.second + 1
                        )
                    )
                }
                else -> return null
            }
        }
    
    
    }
    
    
    6 条回复    2021-05-18 11:57:33 +08:00
    leonme
        1
    leonme  
       2021-05-16 11:11:36 +08:00
    是 kotlin 的代码的可读性本来就不好,还是。。。
    Leviathann
        2
    Leviathann  
    OP
       2021-05-16 12:24:08 +08:00 via iPhone
    @leonme 主要是所有进入递归和二分查找下一次循环的地方都要判定一下有没有到达预设的边界,如果 x 轴到达边界就会退化成 y 轴上的二分查找,y 轴也一样
    然后在对角线上找相邻的两个点哪里必须返回两个坐标也就是四个值,我把每个坐标封装成一个 x 轴和 y 轴索引的 pair 但感觉也没提升什么可读性
    byteli
        3
    byteli  
       2021-05-17 09:52:36 +08:00
    我也是先去搞二分,各种 corner case 折磨的很难受,看了题解的右上解法发现也很快,就直接背下来了。
    不过测时间用 kotlin 这种带虚拟机的是不是不合适
    Leviathann
        4
    Leviathann  
    OP
       2021-05-18 01:16:27 +08:00 via iPhone
    @byteli 是的啊 尤其是对角线二分查找那个地方,中止条件和返回时算左上点和右下点我完全是用他的测试用例调试出来的。。
    Leviathann
        5
    Leviathann  
    OP
       2021-05-18 01:17:58 +08:00 via iPhone
    @byteli 这个时间和空间应该都是同语言的去比的
    byteli
        6
    byteli  
       2021-05-18 11:57:33 +08:00
    @Leviathann 我意思是有 jvm 的话会不会受随机的影响很多呢,预热啊什么的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2251 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:12 · PVG 00:12 · LAX 09:12 · JFK 12:12
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.