题目名称:
杨氏矩阵
题目内容:
有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。
要求:时间复杂度小于O(N);
思路一: 数组行列递增,是有规律的,所以可以遍历数组寻找数字,但是这题有时间复杂度的要求,遍历数组时间复杂度是O(N*2),不满足题意。
思路二: 如图所示,矩阵右上角的数字5是它这一行里最大的,是它这一列里的最小的。
矩阵左下角的数字21是它这一行里最小的,是它这一列里的最大的。
借助这个结论,可以发现,比如要找数字7,它比右上角的数字5大,所以可以排除第一行;比如要找数字23,它比左下角的21大,所以可以排除第一列。
代码如下:
int search(int arr[3][3], int r, int c, int k)
{
int x = 0;
int y = c - 1;
while (x < r && c >= 0)
{
if (k > arr[x][y])
x++;
else if (k < arr[x][y])
y--;
else
return 1;
}
return 0;
}
int main()
{
int arr[3][3] = {1,2,3,4,5,6,7,8,9};
int k = 0;
scanf("%d", &k);
int ret = search(arr,3,3, k);
if (ret == 1)
printf("YES\n");
else
printf("NO\n");
return 0;
}