题目：
杨氏矩阵（一个二维数组，数组的每行从左到右是递增的，每列从上到下是递增的）
在这样的数组中查找一个数字是否存在。
要求时间复杂度小于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 %d\n", *row, *col); } system("pause"); return 0; }
Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx