关于c:杨氏矩阵查找问题

3次阅读

共计 651 个字符,预计需要花费 2 分钟才能阅读完成。

杨氏矩阵阐明:即一个 n * n 的矩阵,从左往右顺次递增,从上往下顺次递增
例如:

就是一个简略的杨氏矩阵当初要查找一个数字是否在该矩阵外部,并且工夫复杂度要小于 O(N), 即不能程序查找首先察看杨氏矩阵的法则,右上角的元素是本列最小,本行最大。因而只有和右上角的元素进行比拟,若被查找元素小于右上角元素,则阐明该元素看到不在右上角元素对应的列,则矩阵能够向左缩减列,若被查找元素大于右上角元素,则阐明该元素不在右上角元素的同一行,则矩阵能够向下缩减一行,依照这个思路迭代的去比拟被查找元素与右上角元素的关系,若在某一次二者相等,则在杨氏矩阵中存在该元素,若找到左下角的元素依然没有找到该元素,则阐明该元素不存在于杨氏矩阵中。同样的思路可用于左下角的元素
代码实现:
int Find_Num(int arr[3][3], int k, int* row, int* col)// 传入一个 3 * 3 的矩阵,并传入被查找元素 k 以及行数的指针,列数的指针
{
    int x = 0;
    int y = *col - 1;
    while (x <= *row - 1 && y >= 0)// 循环终止条件,找到了左下角元素
    {if (arr[x][y] > k)
        {y--;// 若右上角元素大于被查找元素,则向左列查找}
        if (arr[x][y] < k)
        {x++;// 若右上角元素小于被查找元素,则向下行查找}
        else
        {
            *row = x;// 若二者相等,则将该元素的坐标地位返回
            *col = y;
            return 1;
        }
    }
    return 0;
}
注:传入指针的目标是不便扭转内部实参的值,使得内部实参能够获取被查找元素的坐标值
正文完
 0