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

杨氏矩阵阐明:即一个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;
}
注:传入指针的目标是不便扭转内部实参的值,使得内部实参能够获取被查找元素的坐标值

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年99元

阿里云限时活动-1核2G-1M带宽-40-100G ,特惠价87.12元/年(原价1234.2元/年,可以直接买3年),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据