题目描述
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
解题思路
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
我的代码
package arithmetic.mydatabase.day01.arithmetic04;
/*
给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。
给定一个数，判断这个数是否在该二维数组中。
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为 列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。
因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
*/
public class Test {
public static void main(String[] args) {
int a[][] = {
{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}
};
for (int[] x :a){
for (int y:x){
System.out.print(y+" ");
}
System.out.println();
}
int i=5;
Test test = new Test();
boolean find = test.Find(i, a);
System.out.println(find);
}
public boolean Find(int target,int [][] matrix){
if (matrix==null || matrix.length ==0|| matrix[0].length==0)//可行性判断
return false;
int rows = matrix.length;//行
int cols = matrix[0].length; //列
// 我们从右上角开始
int r=0,c=cols-1;
while ( r<=cols-1 && c>=0 ){//可行性判断
if (target == matrix[r][c])
return true;
else if (target > matrix[r][c])
r++;
else
c--;
}
return false;
}
}
我的做题思路
如解题思路
数据从左至右增大，从上到下增大，如果我们需要找到一个数是否是在该数组中，我们就需要与右上角的数据比较，如果比该数大，我们的行下标+1否则列下标-1，以此类推如果有冲突（即是移动比较的数组后发现下标回退为上一个数据，说明数组中没有我们需要的数据）
进数据后我们先进行可行性判断
if (matrix==null || matrix.length ==0|| matrix[0].length==0)//可行性判断 验证该数组是否真实存在
然后我们进行标注，标注该二维数组的行和列
int rows = matrix.length;//行
int cols = matrix[0].length;//列
此时，我们从右上角开始
即是
int r=0,c=cols-1;
然后我们进行可行性判断（防止数组下标越界）
while ( r<=cols-1 && c>=0 ){//可行性判断
如果 我们设定的值和数组中当前的值相同
我们返回true
if (target == matrix[r][c]) return true;
如果我们设定的值比数组当前的值大
此时行数+1 继续循环
else if (target > matrix[r][c]) r++;
如果我们设定的值比数组当前的值小
此时列数-1 继续循环
else c--;
如果都没有找到则返回为false
