题目:
请编写一个程序,在杨氏矩阵中查找某个数字是否存在。
要求:时间复杂度小于O(N);
杨氏矩阵 :一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的。
代码实现:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
struct point
{
int x;
int y;
};
struct point Search(int arr[3][3], int rows, int cols, int num)
{
assert(arr);
struct point ret = { -1, -1 };
int x = 0;
int y = cols - 1;
while (x <= rows && y >= 0)
{
if (num > arr[x][y])
{
x++;
}
else if (num < arr[x][y])
{
y--;
}
else
{
ret.x = x;
ret.y = y;
return ret;
}
}
return ret;
}
int main()
{
int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int input = 0;
printf("请输入您要查找的数:");
//输入
while (scanf("%d", &input) == 1)
{
//处理
struct point ret = Search(arr, 3, 3, input);
//输出
if (ret.x >= 0 && ret.y >= 0)
{
printf("%d的下标的是%d %d\n", input, ret.x, ret.y);
}
else
{
printf("该数在次杨氏矩阵中不存在\n");
}
}
return 0;
}