做网站 图文教程,ps做登录网站,wordpress打电话插件,国内个人网站建设记录《剑指offer》上的算法题。完整的代码例子可以在我的Github 题目#xff1a;在一个二维数组中#xff0c;每一行按照从左到右递增的顺序排序#xff0c;每一列都按照从上到下递增的顺序排。请完成一个函数#xff0c;输入这样的一个二维数组和一个整数#xff0c;判断…记录《剑指offer》上的算法题。完整的代码例子可以在我的Github 题目在一个二维数组中每一行按照从左到右递增的顺序排序每一列都按照从上到下递增的顺序排。请完成一个函数输入这样的一个二维数组和一个整数判断数组中是否含有这个整数。 下面给出一个题目所要求的二维数组
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
这道题目的解法是选择右上角或者左下角的数组元素来进行查找。比如以选择右上角的数组元素为例当选择的数值大于要查找的整数值如上述数组中的9要查找的是7那么9是第四列的最小值所以这样就排除了第四列7就应该存在前三列中这个时候就选择前三列数组的右上角也就是9左边的8然后8还是大于7进一步排除第三列继续选择前两列的右上角元素–2这个时候2就小于7那么7应该是位于2的右边或者下边但右边已经查找过并且被剔除了所以就只有其下边的这种可能性此时就剔除第一行了选择剩下的第二行到第四行和前两列的区域的右上角元素–44还是小于7然后同样剔除所在的行往下查找然后就找到7了。
总结上述查找的规律首先选择数组中右上角的数字。如果该数字等于要查找的数字查找过程结束如果该数字大于要查找的数字剔除这个数字所在的列如果该数字小于要查找的数字剔除这个数字所在的行。通过这样的查找每次查找都可以剔除一行或者一列每一步都可以缩小范围直到查找到所查找的数字或者发现查找的数字不存在数组中。
下面是给出实现的函数代码和测试代码
// 二维数组的查找
bool Find(int* matrix, int rows, int columns, int number){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] number){found true;break;}else if (matrix[row * columns column] number)column--;elserow;}}return found;
}
// 测试
int main(void){int rows 4;int columns 4;int a[4][4] {{ 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, {6, 8, 11, 15}};int *matrix a[0];// 二维数组包含查找的数字cout find 7 in matrix: Find(matrix, rows, columns, 7) endl;// 二维数组不包含查找的数字数字大于数组的最大值cout find 16 in matrix: Find(matrix, rows, columns, 16) endl;// 二维数组不包含查找的数字数字小于数组的最小值cout find 0 in matrix: Find(matrix, rows, columns, 0) endl;// 二维数组不包含查找的数字数字介于数组最大值和最小值之间cout find 3 in matrix: Find(matrix, rows, columns, 3) endl;int *matrix_null NULL;// 测试输入空指针的情况cout find 7 in matrix: Find(matrix_null, rows, columns, 7) endl;system(pause);return 0;
}
选择左下角的数字也是可以实现同样的效果只是这种情况所剔除是行还是列刚好相反当这个数字大于所查找的数字是剔除这个数字所在的行这个数字小于所查找的数字剔除这个数字所在的列。
