//杨氏矩阵 【每行从左到右,每列从上到下增加】
有一个二维数组.
数组的每行从左到右是递增的,每列从上到下是递增的.
在这样的数组中查找一个数字是否存在。
时间复杂度小于O(N);【不能挨个查,挨个查时间复杂度=o(n)】
//
//数组:
//1 2 3
//2 3 4
//3 4 5
//
//
//1 3 4
//2 4 5
//4 5 6
//struct Ret
//{
//int x;
//int y
//};
(struct Ret)int IsExit(int arr[3][3], int k,int row,int col)
{
int x = 0;
int y = col - 1;
//struct Ret ret = { -1,-1 };
while((x<row) && (y>=0))
{
if (k>arr[x][y])
{
x++;
}
else if (k == arr[x][y])
{
return 1;
//ret.x=x;
//ret.y = y;
//return ret;
}
else
y--;
}
return 0;
}
int main()
{
int arr[3][3] = { 1, 3, 4, 2, 4, 5, 4, 5, 6 };
int key = 4;
struct Ret ret = { 0 };
int ret = IsExit(arr, key,3,3);
if (ret = 1)
{
printf("存在\n");
}
else
{
printf("不存在\n");
}
system("pause");
return 0;
}