面试题——二维数组中的查找
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7,则返回true;如果查找数字5,由于数组不含有该数字,则返回false。
这是前两天解决的一个问题,写出来总结一下。
递归函数如下,对于查找矩阵,递归如下算法。
对这个矩阵,从左上向右下方向查找。
0. 如果当前位置(m, n)的数据等于所求数据,查找成功。
1. 如果当前位置(m, n)的数据小于所求数据,说明(i <=m && j<=n)位置的数据均小于所求数据。淘汰。则查找(m + 1, n + 1)。
2. 如果当前位置(m, n)的数据大于所求数据,则(i >m && j>n)位置的数据均大于所求数据。淘汰。则对(i<m && j>=n)以及(i<=m&&j<n)两个矩阵递归查找。
3. 考虑情况,某个矩阵是1*n或n*1的,也就是一行或一列,那么就不要按对角线查找了,按大小遍历查找即可。
4. 需考虑矩阵行列不相等情况,比如行到了边缘,而列没有。当前数据还小于所查数据,那么淘汰调这半边即可,对剩下那半个矩阵递归查找。
时间紧,所述简略,见谅,代码附上。
#include<iostream> using namespace std; int data[100][100]; //参数:所查原始大矩阵行边界,列边界,所查矩阵块的上边界,下边界,左边界,右边界,所查数据。 int search(int bound_r, int bound_c, int left_i, int right_i, int left_j, int right_j, int find_num){ int i = 0; int j = 0; if(left_i < 0 || left_i > bound_r || right_i < 0 || right_i > bound_r || left_j < 0 || left_j > bound_c || right_i < 0 || right_i > bound_c) return 0; if(left_j == right_j){ //矩阵为一列 for(i = left_i; i <= right_i && data[i][right_j] <= find_num; i++){ if(data[i][right_j] == find_num){ cout << i << " " << right_j << endl; return 1; } } return 0; } if(left_i == right_i){ //矩阵为一列 for(j = left_j; j <= right_j && data[right_i][j] <= find_num; j++){ if(data[right_i][j] == find_num){ cout << right_i << " " << j << endl; return 1; } } return 0; } for(i = left_i, j = left_j; i <= right_i && j <= right_j; i++, j++){ //正常矩阵 if(data[i][j] == find_num){ cout << i << " " << j << endl; return 1; } else if(data[i][j] > find_num){ return search(bound_r, bound_c, left_i, i - 1, j, right_j, find_num) + search(bound_r, bound_c, i, right_i, left_j, j - 1, find_num); } } if(j <= right_j && i > right_i){ //行出界,排除一块矩阵,对另一块查 return search(bound_r, bound_c, left_i, right_i, j, right_j, find_num); } if(i <= right_i && j > right_j){ //列出界,排除一块矩阵,对另一块查 return search(bound_r, bound_c, i, right_i, left_j, right_j, find_num); } } int main(){ freopen("test.txt", "r", stdin); int i = 0; int j = 0; for(i = 0; i < 4; i++){ for(j = 0; j < 7; j++){ cin >> data[i][j]; } } search(3, 6, 0, 3, 0, 6, 17); // search(3, 3, 0, 3, 0, 3, 8); return 0; }