Search a 2D Matrix详解编程语言
编程语言 详解 search 2D matrix
2023-06-13 09:11:53 时间
Problem
Write an efficient algorithm that searches for a value in an m x n matrix.
This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. ExampleConsider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]
Given target = 3, return true.
ChallengeO(log(n) + log(m)) time
题解: 一次二分搜索 VS 两次二分搜索 一次二分搜索 由于矩阵按升序排列,因此可将二维矩阵转换为一维问题。对原始的二分搜索进行适当改变即可(求行和列)。时间复杂度为 O(log(mn))=O(log(m)+log(n)) 两次二分搜索 先按行再按列进行搜索,即两次二分搜索。时间复杂度相同。显然我们应该选择一次二分搜索,直接上 lower bound 二分模板。
Java:public class Solution { /** * @param matrix, a list of lists of integers * @param target, an integer * @return a boolean, indicate whether matrix contains target public boolean searchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0] == null) { return false; int ROW = matrix.length, COL = matrix[0].length; int lb = -1, ub = ROW * COL; while (lb + 1 ub) { int mid = lb + (ub - lb) / 2; if (matrix[mid / COL][mid % COL] target) { lb = mid; } else { if (matrix[mid / COL][mid % COL] == target) { return true; ub = mid; return false; }
仍然可以使用经典的二分搜索模板(lower bound),注意下标的赋值即可。
首先对输入做异常处理,不仅要考虑到matrix为null,还要考虑到matrix[0]的长度也为0。 由于 lb 的变化处一定小于 target, 故在 else 中判断。 复杂度分析二分搜索,O(logn).
20716.html
cgojava相关文章
- Go 编程语言的真正优势是什么?
- SpringBoot集成Quartz实现定时器详解编程语言
- js,jquery发送短信倒计时实现代码详解编程语言
- Elastic Search Java Api 创建索引结构,添加索引详解编程语言
- Java 中的 Image 实例转成 BufferedImage 实例详解编程语言
- C++运算符的重载详解编程语言
- 欢迎购买《Kafka源码解析与实战》详解编程语言
- 原生JS封装时间运动函数详解编程语言
- Go 处理yaml类型的配置文件详解编程语言
- mybatis 模糊查询简单sql详解编程语言
- JSTL的fn函数详解编程语言
- Java遍历文件夹下所有文件并替换指定字符串详解编程语言
- Java中关于String类型你不知道的几个问题详解编程语言
- 第一段自动化测试代码详解编程语言
- Javascript实现页面跳转的几种方式详解编程语言
- Java HSSFworkbook,XSSFworkbook,SXSSFworkbook区别简述详解编程语言
- Java IO(三):字节流详解编程语言
- PHP for的1个问题详解编程语言
- ECC TO HANA FAGLB03 search-help on Account Number field doesn’t working or not returning the selected value to the Account Number field.详解编程语言
- BINARY SEARCH 的一点说明详解编程语言
- SAP 物料在启用序列号管理或者不启用序列号管理之间快速切换详解编程语言
- abap中利用BINARY SEARCH 二分法查找内表记录时注意项详解编程语言
- ABAP中BINARY SEARCH详解编程语言
- Search a 2D Matrix II详解编程语言
- Binary Search – 二分查找详解编程语言
- Elastic Search操作入门详解编程语言