Write an efficient algorithm that searches for a value in an m x n 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.

还没有评论

举报纠错

切换

1 个答案

public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int c = matrix[0].length; int r = matrix.length; int i = 0; //从右上角的元素向下寻找第一个大于target的元素下标 while (i < r && matrix[i][c-1] < target) { i++; } if (i != r) { //若找到该下标，从该元素开始向左搜索target int j = c - 1; while (j >= 0 && matrix[i][j] != target) { j--; } if (j >= 0) { return true; } } return false; } }

还没有评论

切换

撰写答案

扫描后移动端查看本题

我也分享一个题目