Leetcode 240 剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路 matrix每一列最右邊是最大 初始化: i代表row j代表col 一開始先把i設為第0 row j設最右邊欄位matrix[0].length - 1
- 用while去繞行i跟j，但要設置i與j繞行的邊界範圍
- target先比最右欄，若matrix[i][最右欄]比target大，代表要把最右欄 去掉，最右欄往左移j–
- 若matrix[i][最右欄]比target小，代表此列的值不是搜尋範圍，移到下一個row i++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//限制條件
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
//初始化
int row = matrix.length - 1;
int col = matrix[0].length - 1;
int i = 0;
int j = col;//j設最右邊欄位matrix[0].length - 1
while(i >= 0 && i <= row && j >= 0 && j <= col) { //1
//System.out.printf("i = %d , j = %d , num = %d \n", i , j, matrix[i][j] );
if(matrix[i][j] == target) {
return true;
} else if (target < matrix[i][j]) { //2
j--;
} else if (target > matrix[i][j]) { //3
i++;
}
}
return false;
}
}