C语言达成在杨氏矩阵中查找数字
发布时间：2021-12-05 12:12:19 所属栏目：教程 来源：互联网
导读：题目： 杨氏矩阵（一个二维数组，数组的每行从左到右是递增的，每列从上到下是递增的） 在这样的数组中查找一个数字是否存在。 要求时间复杂度小于O(N); 主要思路： 题目要求时间复杂度度不能大于O(N)，所以判断次数必须小于遍历一次数组次数。 所以从数组的
|
题目： 杨氏矩阵（一个二维数组，数组的每行从左到右是递增的，每列从上到下是递增的） 在这样的数组中查找一个数字是否存在。 要求时间复杂度小于O(N); 主要思路： 题目要求时间复杂度度不能大于O(N)，所以判断次数必须小于遍历一次数组次数。 所以从数组的右上角开始判断，若当前元素大于要查找的数字，则跳过当前列查询下一列，若当前元素小于要查找的数，则跳过当前行查找下一行，直至找到或者找不到。 eg： 此处使用数组arr[3][3]={1，2，3，4，5，6，7，8，9}； 1 2 3 4 5 6 7 8 9 在数组中朝查找5，首先判断3<5,则查找范围就变成了 4 5 6 7 8 9 再判断6>5,则查找范围又变为了 4 5 7 8 这时候再判断5=5 则找到 源代码: #include<stdio.h> #include<stdlib.h> void find(int arr[][3],int *row, int *col,int key) { int x = 0; int y = *col - 1; while (x <*row&&y>0)//判断条件 { if (arr[x][y] == key)//找到 { *row = x; *col = y; return; } else if (arr[x][y] < key) { x++;//变换行 } else { y--;//变换列 } } *row = -1; *col = -1; } int main() { int arr[3][3]= {1,2,3,4,5,6,7,8,9}; int x=3; int y=3; int *row = &x; int *col = &y; int key=5; find(arr,row,col,key); if (*row == -1 && *col == -1) { printf("没找到n"); } else { printf("找到了，下标为%d %dn", *row, *col); } system("pause"); return 0; }  （编辑：玉林站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
