C语言面试C++二维数组中的查找示例 C语言面试C++二维数组中的查找

二维数组中的查找

面试题3：
暴力遍历
动态基点操作

二维数组中的查找
面试题3：

文章图片

似题:
我做过这个类似的有杨氏矩阵为背景的，实际上是一样的

暴力遍历
二维数组暴力遍历的话时间复杂度为O(n2)
虽然暴力但是应付学校考试这个就是一把好手

#include//const 就是因为二维数组是定死的int search(const int arr[4][4], int num,unsigned int* prow,unsigned int* pcol){ int i = 0; //扫描行 for (i = 0; i < *prow; i++) {//扫描列int j = 0; for (j = 0; j < *pcol; j++){//与所查数比较判断，有一样的就直接返回if (arr[i][j] == num){*prow = i; //把坐标传回去*pcol = j; return 1; //一次返回，之后就不看了，因为已经证明到有这个数了，没必要在做无用功了}} } return 0; }int main(){ int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} }; int num = 0; while (1) {unsigned int row = sizeof(arr) / sizeof(arr[0]); unsigned int col = sizeof(arr[0]) / sizeof(arr[0][0]); //把row，col拉进来就是为了每次再来是更新一次//长宽，因为下面我们就是用row，col变量没有用其他变量printf("请输入你想要找的数:>"); scanf("%d", &num); if (search(arr, num, &row, &col))//把长宽传地址过去用指针prow，pcol接收{printf("有这个数\n"); printf("坐标为(%d,%d)\n", row, col); }else{printf("没有这个数\n"); } } return 0; }

文章图片

动态基点操作
【C语言面试C++二维数组中的查找示例】暴力操作肯定拿不下面试官的心，没有思想，应该优化程序，减小时间复杂度

文章图片

文章图片

然后把上面search函数改改就可以了
时间复杂度也降为O(n)

#include//const 就是因为二维数组是定死的int search(const int arr[4][4], int num,unsigned int* prow,unsigned int* pcol){ int i = 0; unsigned int x = 0; unsigned int y = *pcol-1; while ((x<*prow)&&(y>=0)) {if (arr[x][y] - num > 0){y--; }else if (arr[x][y] - num < 0){x++; }else{*prow = x; *pcol = y; return 1; } } return 0; }int main(){ int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} }; int num = 0; while (1) {unsigned int row = sizeof(arr) / sizeof(arr[0]); unsigned int col = sizeof(arr[0]) / sizeof(arr[0][0]); //把row，col拉进来就是为了每次再来是更新一次//长宽，因为下面我们就是用row，col变量没有用其他变量printf("请输入你想要找的数:>"); scanf("%d", &num); if (search(arr, num, &row, &col))//把长宽传地址过去用指针prow，pcol接收{printf("有这个数\n"); printf("坐标为(%d,%d)\n", row, col); }else{printf("没有这个数\n"); } } return 0; }