题解 | #二维数组中的查找#杨氏矩阵
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
本题典型的杨氏矩阵问题
解题思路：
在m*n的数组arr中（杨氏矩阵），第m行的第1列数字和第n列的第1行数字是比较又特点的，arr[m-1][0]>arr[m-2][0](他的上一行的同一列的数小于它，即纵向递增），arr[m-1][0]M<arr[m-1][1](他的同一行的下一个数大于它，即横向递增）
我们可以以这样一个性质去设计解题思路。
从第m行的第1列开始。
1.只要target(目标值)>arr[i][col]，那么就执行操作col++(arr需要增加)；
2.如果target(目标值)<arr[i][col]，那么就执行操作i--(因为此矩阵从上到下增加，所以i--是从下到上减少，arr的值需要减小）；
3.如果target(目标值)=arr[i][col]，直接返回true。
要执行上述三个选择结构就需要用到循环结构，不难想到循环结构的终止条件如下：
①i>=0，即当执行到第1行第1列的时候（因为第1行的下标等于0，所以包含i=0），当执行到arr[0][0]的时候终止（到本二维数组中最小的数的时候）,也就意味着目标值比本二维数组最小值还要小；
②col<arr的列数，当执行到arr[m-1][n-1]斜对角的时候终止（到本二维数组中最大的数的时候）,也就意味着目标值比本二维数组最大值还要大。
分布图如下：
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
int i=arrayRowLen-1,col=0;
while(i>=0&&col<*arrayColLen){
if(array[i][col]>target){
i--;
}else if(array[i][col]<target){
col++;
}else{
return true;
}
}
return false;
}
查看24道真题和解析
