题目
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数
举例:下面的二维数组每行、每列都递增排序。若在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
image.png
解题思路
- 首先选取数组右上角的数字9.因为数组中每一行都按照从左到右递增,每一列从上到下递增。所以7<9,也就是7不可能出现在9所在的列,故把这一列踢出。同理,可以把9对应的列也剔除
- 这样剩余的两列组成的数组中,数字2位于数组的右上角,因为右边已没有元素,所以7只能在2的下边,可以把2对应的行剔除。同理把4对应的行剔除
- 在剩余的两行两列中,刚好位于右上角的是需要查找的数字7
代码
- 细节
- 二维数组的初始化
int matrix[][4]={{1,2,8,9},
{2,4,9,12},
{4,7,10,13},
{6,8,11,15}};
- 二维数组为函数参数退化为数组的指针(一维数组指针)
一维数组 char a[30] 指针 char*
指针数组 char *a[30] 指针的指针 char **a
二维数组 char a[10][30] 数组的指针 char(*a)[30]
- 代码
class Solution{
public:
bool numInmatrix(int *matrix,int num,int rows,int columns)
{
bool found = false;
if(matrix != NULL && rows>0 && columns >0)
{
int row = 0;
int column = columns-1;
while(row<rows && column >=0)
{
if(matrix[row*columns+column] == num)
{
found = true;
break;
}
else if(matrix[row*columns+column] > num)
{
--column;
}
else
{
++row;
}
}
}
return found;
}
};
网友评论