C++二维数组中的查找 C语言面试C++二维数组中的查找示例
小码农UU 人气:0想了解C语言面试C++二维数组中的查找示例的相关内容吗，小码农UU在本文为您仔细讲解C++二维数组中的查找的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：C语言面试,C++二维数组中的查找，下面大家一起来学习吧。
二维数组中的查找
面试题3：
似题:
我做过这个类似的有杨氏矩阵为背景的，实际上是一样的
暴力遍历
二维数组暴力遍历的话时间复杂度为O(n2)
虽然暴力但是应付学校考试这个就是一把好手
#include<stdio.h>
//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;
}
动态基点操作
暴力操作肯定拿不下面试官的心，没有思想，应该优化程序，减小时间复杂度
然后把上面search函数改改就可以了
时间复杂度也降为O(n)
#include<stdio.h>
//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;
}
结果也是不错的
加载全部内容