【C语言】杨氏矩阵

题目描述：

有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某个数字是否存在。

要求：时间复杂度小于O(N);

思路1：可以采用遍历方式一个个查找，但是这样时间复杂度为O(N)不满足题目要求

思路2：

1. 先观察整个数组，从四个角落出发，会发现左上角和右下角向两侧都是递增（递减）的，而右上角和左下角是向两侧增减趋势不同的。

1. 选取右上角（当然左下角也可以），会发现，每一行中最右边数字都是最大的，因此只需要将最右侧数字与要找到数字k进行比较，若比k小则说明一整行都比k小，纵坐标不变，横坐标+1跳至下一行查找；若比k大则可能在其左侧有与k相等的数字，横坐标不变，纵坐标-1往左侧查找。

• 当然杨氏矩阵并不一定数组中所以元素都是依次递增的，如下图数组，会发现时间复杂度也是小于O(N)的，所以此方法是可行的。

最终代码实现：

void search(int(*arr)[4], int r, int c, int k)
{
    int i = 0,sign=0;
    int x = 0;
    int y = c - 1;
    while (y>=0&&x<r)
    {
        if (arr[x][y] < k)
        {
            y++;
        }
        else if (arr[x][y] > k)
        {
            x--;
        }
        else
        {
            sign = 1;
            printf("找到了\n");
            break;
        }
    }
    if (sign == 0)
        printf("没有找到\n");

}

int main()
{
    int arr[3][4] = { {2,3,4},{5,7,8},{9,12,14} };
    int k=0;
    printf("请输入要查找的数字->");
    scanf("%d", &k);
    search(arr, 3, 4,k);
    return 0;
}

我们还可以显示出找到数字的坐标，代码改进：

int search(int arr[3][4],int* a, int* b,int k)
{
    int x = 0;
    int y = *b-1;
    //定位右上角元素
    while (y>=0&&x<*a-1)
    {
        if (arr[x][y] < k)
        {
            x++;
        }
        else if (arr[x][y] > k)
        {
            y--;
        }
        else
        {
            *a = x;
            *b = y;
            return 1;
        }
    }
    return 0;

}

int main()
{
    int arr[3][4] = { {2,3,4,6},{5,7,8,9},{8,9,12,14} };
    int k=0;
    printf("请输入要查找的数字->");
    scanf("%d", &k);
    int a = 3;
    int b = 4;
    int ret=search(arr,&a,&b,k);
    if (ret == 1)
    {
        printf("找到了，坐标为（%d,%d）\n", a, b);
    }
    else
        printf("找不到\n");
    return 0;
}