题目要求://杨氏矩阵
有一个二维数组.
数组的每行从左到右是递增的,每列从上到下是递增的.
在这样的数组中查找一个数字是否存在。
时间复杂度小于O(N); (题目出自剑指offer,曾经是华为的面试题)
例如:数组:
1 2 3
4 5 6
7 8 9
代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <stdlib.h>
//方法一:最简单最挫的解法
int main()
{
int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int i = 0;
int j = 0;
int key = 0;
int x = 3;
int y = 3;
printf("请输入要查找的数:");
scanf("%d", &key);
for (i = 0; i < x; i++)
{
for (j = 0; j < y;j++)
if (key == arr[i][j])
printf("找到了\n");
else
printf("找不到\n");
}
return 0;
}
方法二:
struct Ret
{
int x;
int y;
};
struct Ret search(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])
{
ret.x = x;
ret.y = y;
return ret;
}
else
{
y--;
}
}
return ret;
}
int main()
{
int arr[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int key = 0;
printf("请输入要查找的数:");
scanf("%d", &key);
struct Ret ret = {0};
ret = search(arr, key,3,3);
if (ret == 1)
printf("找到了\n");
else
printf("找不到\n");
system("pause");
return 0;
}
//方法三
int search(int arr[3][3], int k, int* px, int *py)
{
int x = 0;
int y = *py-1;
while((x<*px)&&(y>=0))
{
if(k>arr[x][y])//
{
x++;
}
else if(k == arr[x][y])//找到了打印位置
{
*px = x;
*py = y;
printf("x=%d y=%d\n",x,y);
return 1;
}
else
{
y--;
}
}
//如果找不到返回{-1,-1}
*px = -1;
*py = -1;
}
int main()
{
int arr[3][3] = {1,2,3,4,5,6,7,8,9};
int key =0;
printf("请输入要查找的数:");
scanf("%d", &key);
int ret = 0;
int x = 3;
int y = 3;
ret=search(arr, key, &x, &y);
if (ret==1)
printf("找到了\n");
else
printf("找不到\n");
system("pause");
return 0;
}
本人初出茅庐,编程能力匮乏,望各路大牛指正