題目
在一個二維數(shù)組中龙助，每一行都按照從左到右遞增的順序排序捉邢，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)吮螺，輸入這樣的一個二維數(shù)組和一個整數(shù)饶囚，判斷數(shù)組中是否含有該整數(shù)
舉例:下面的二維數(shù)組每行、每列都遞增排序鸠补。若在這個數(shù)組中查找數(shù)字7萝风，則返回true；如果查找數(shù)字5莫鸭，由于數(shù)組不含有該數(shù)字闹丐，則返回false。
image.png
解題思路
- 首先選取數(shù)組右上角的數(shù)字9.因為數(shù)組中每一行都按照從左到右遞增被因，每一列從上到下遞增卿拴。所以7<9，也就是7不可能出現(xiàn)在9所在的列梨与，故把這一列踢出堕花。同理，可以把9對應(yīng)的列也剔除
- 這樣剩余的兩列組成的數(shù)組中粥鞋，數(shù)字2位于數(shù)組的右上角缘挽，因為右邊已沒有元素，所以7只能在2的下邊，可以把2對應(yīng)的行剔除壕曼。同理把4對應(yīng)的行剔除
- 在剩余的兩行兩列中苏研，剛好位于右上角的是需要查找的數(shù)字7
代碼
- 細節(jié)
- 二維數(shù)組的初始化
int matrix[][4]={{1,2,8,9},
{2,4,9,12},
{4,7,10,13},
{6,8,11,15}};
- 二維數(shù)組為函數(shù)參數(shù)退化為數(shù)組的指針(一維數(shù)組指針)
一維數(shù)組 char a[30] 指針 char*
指針數(shù)組 char *a[30] 指針的指針 char **a
二維數(shù)組 char a[10][30] 數(shù)組的指針 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;
}
};
