剑指04-二维数组中的查找
2022/4/1 23:24:24
本文主要是介绍剑指04-二维数组中的查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:剑指 Offer 04. 二维数组中的查找(M)
解题思路1:暴力遍历
直接两个for循环,本来是想用二分的,但是常规二分没法确定后续的划分范围,直接暴力遍历
时间:\(O(MN)\)
空间:\(O(1)\)
class Solution: def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool: if not matrix or not matrix[0]: return False for i in matrix: for j in i: if target == i: return True return False
优质解答:改版二分查找(参考自K神)
利用数组从上到下和从左到右都为递增的特点,从数组右上角开始,每次缩小一行或者一列的范围,如果target大于该值,则可以直接向下移动一行,如果target小于该值,则可以向左移动一列,直到找到target或者遍历结束。
时间:\(O(M+N)\)
空间:\(O(1)\)
class Solution: def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool: i = 0 if len(matrix) == 0: return False j = len(matrix[0]) - 1 while i < len(matrix) and j >= 0: if matrix[i][j] == target: return True elif matrix[i][j] < target: i += 1 else: j -= 1 return False
这篇关于剑指04-二维数组中的查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?