74. Search a 2D Matrix

74. Search a 2D Matrix

最佳答案 53678位专家为你答疑解惑

74. Search a 2D Matrix

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, returntrue.

public class Solution {    public boolean searchMatrix(int[][] matrix, int target) {        int row=matrix.length,col=matrix[0].length;        int i=0,j=col-1;        while(i<row&&j>=0)        {            if(target>matrix[i][j])               i++;            else if(target<matrix[i][j])               j--;            else               return true;        }        return false;            }}

Go语言实现LeetCode算法：74 二维矩阵搜索

1 题目描述

对m x n整数矩阵，写一个对某值进行高效搜索的算法。该矩阵有如下特征：

a）每行数值自左向右是有序的；

b）每行第一个数比上一行最后一个数大。

例子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

题目出处：

https://leetcode.com/problems/search-a-2d-matrix/

2 解决思路

a）对于给定目标值，首先对二维矩阵每行在左边第一列进行二分搜索，以确定目标值在哪一行；

b）确定目标值在哪一行后，然后在该行进行二分搜索即可。

该算法的整体复杂度为O(log(M))+O(log(N))。

下面先温故一下对整数数组的二分搜索。

3 温故二分搜索

这样针对本题目，进行两次二分搜索即可。

4 算法Golang完整实现代码

https://github.com/olzhy/leetcode/blob/master/74_Search_A_2D_Matrix/test.go

原文链接：https://leileiluoluo.com/posts/leetcode-search-a-2d-matrix.html

本文作者：磊磊落落的博客，原创授权发布