前言
这道题目只需要一些简单的java语法知识,就可以看懂。
题目
leetcode-74 在二维数组中搜索一个数
分类(tag):二分查找这一类
英文链接:
https://leetcode.com/problems/search-a-2d-matrix/
中文链接:
https://leetcode-cn.com/problems/search-a-2d-matrix/
题目详述
编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
示例 1:
输入:matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3输出: true
示例 2:
输入:matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13输出: false
题目详解
第一种方法
思路
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0)
return false;
int rowIndex = 0;//代表下标
int colIndex = matrix[0].length - 1;//代表下标
while(rowIndex < matrix.length && colIndex >=0)
{
if(target == matrix[rowIndex][colIndex])
return true;
else if(target > matrix[rowIndex][colIndex])
rowIndex++;
else
colIndex--;
}
return false;
}
}
代码11到12行就是思路中第一步的体现,13-14行就是思路中第二步的体现。
第二种方法
思路
代码
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0)
return false;
int n = matrix[0].length;
int left = 0;
int right = matrix.length*matrix[0].length - 1;
while(left <= right)
{
int mid = left + (right - left) / 2;
if(target == matrix[mid/n][mid%n])
return true;
else if(target < matrix[mid/n][mid%n])
right = mid - 1;
else
left = mid + 1;
}
return false;
}
}
我举一个例子方便大家理解。
示例 1:
输入:matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3输出: true
结果展示
5ms的是二分查找的结果,比《剑指offer》还快了2ms。
结束语
每天一刷leetcode,10.28号打卡~