[算法][LeetCode]Search a 2D Matrix——二维数组的二分查找
2024-08-21 16:27:59
题目要求
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.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3
, return true
.
分析
一开始写的时候把他拆分成了两个二分查找,先纵向找,再横向找。纵向的二分查找比较复杂,要确定是在某个坐标上,或者在两个坐标之间。
后来找到一个更好的方法,就是把二维数组的坐标转化成一位数组,整体进行二分查找,程序更简单,复杂度也更低了。
Java代码
public boolean searchMatrix(int[][] matrix, int target) { if (matrix.length == 0 || matrix[0].length == 0) {
return false;
} int xLength = matrix[0].length;
int min = 0;
int max = matrix[0].length * matrix.length - 1; int x, y, current;
while (min <= max) {
current = (min + max) / 2;
y = current / xLength;
x = current % xLength;
if (matrix[y][x] == target) {
return true;
} else if (target < matrix[y][x]) {
max = current - 1;
} else {
min = current + 1;
}
} return false;
}
最新文章
- 【转载】兼容php5,php7的cURL文件上传示例
- Ext.NET MVC 配置问题总结
- 复旦大学2015--2016学年第二学期高等代数II期末考试情况分析
- ARCGIS server没有服务、silverlight不能调试、windows server2008安装时跳出“安装程序无法创建新的系统分区也无法定位现有的系统分区”的解决方案
- opengl基础学习专题 (二) 点直线和多边形
- D&;F学数据结构系列——插入排序
- centos coreseek 快速安装
- wordpress4.0.1源码学习和摘录--项目设置
- Linux下Samba的配置
- URL中#(井号)的作用(转)
- 写一个python的服务监控程序
- API手册(2017)
- 安装Linux Mint 17后要做的20件事
- The Little Prince-12/11
- (原创)如何使用boost.asio写一个简单的通信程序(一)
- 软件安装的list(0918)
- POJ 1753 bfs+位运算
- 一个简单 Go Web MVC 框架实现思路
- Maven项目使用阿里云的Maven库
- springcloud16---zuul-filter