FilesExpand file tree

 master

/

offer04.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

38 lines (37 loc) · 1.45 KB

 master

/

offer04.java

Copy path

Top

File metadata and controls

• Code
• Blame

38 lines (37 loc) · 1.45 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

/**

* [04] 二维数组中的查找

*

* 题目：判断矩阵中是否含有整数 target （矩阵中每一行从左往右递增, 每一列从上往下递增）。

*

* 思路：从左下角往右上角判断（或从右上角往左下角判断）。

* 1。若从左下角开始查找，小于当前元素的数一定不在在其右边，大于当前元素的数一定不在其上边，所以可以根据 target 和当前元素的大小关系

* 来缩小查找区间。

* 2。若从右上角往左下角判断同理。

*/

class Solution {

/**

* 时间复杂度：O(n + m) (n 为矩阵的行数，m 为矩阵的列数)

* 空间复杂度：O(1)

*/

public boolean findNumberIn2DArray1(int[][] matrix, int target) {

if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {

return false;

}

// search from left bottom to right top.

int rows = matrix.length, cols = matrix[0].length;

int row = rows - 1, col = 0;

while (row >= 0 && col < cols) {

if (matrix[row][col] == target) {

// trap target.

return true;

} else if (matrix[row][col] < target) {

// if current element is smaller than target, move right.

col++;

} else {

// if current element is bigger than target, move up.

row--;

}

}

return false;

}

}