教育改变生活

标题: LeetCode真题-矩阵查找 [打印本页]

作者: 一秉 时间: 2020-8-20 00:04
标题: LeetCode真题-矩阵查找
题目描述
请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：
每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大
例如：
对于下面的矩阵：

[
[1, 3,  5,  7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

要搜索的目标值为3，返回true；
示例1
输入：[[1,1]],0
输出：false
实现代码：
import java.util.*;

public class Solution {
/**
   *
   * @param matrix int整型二维数组
   * @param target int整型
   * @return bool布尔型
   */
public boolean searchMatrix (int[][] matrix, int target) {
      // write code here
      if(matrix==null||matrix.length==0||matrix[0].length==0)
         return false;
      int row=matrix.length;
      int col=matrix[0].length;
      int start=0,end=row*col-1;
      while(start<=end){
         int mid=(start+end)/2;
         int value=matrix[mid/col][mid%col];
         if(value>target){
            end=mid-1;
         }else if(value<target){
               start=mid+1;
         }else{
               return true;//找到了value==target
         }
      }
      return false;
      }
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)