C语言实现在杨氏矩阵中查找数字

栏目: C · 发布时间: 5年前

内容简介:题目:杨氏矩阵(一个二维数组,数组的每行从左到右是递增的,每列从上到下是递增的)在这样的数组中查找一个数字是否存在。

题目:

杨氏矩阵(一个二维数组,数组的每行从左到右是递增的,每列从上到下是递增的)

在这样的数组中查找一个数字是否存在。

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

主要思路:

题目要求时间复杂度度不能大于O(N),所以判断次数必须小于遍历一次数组次数。

所以从数组的右上角开始判断,若当前元素大于要查找的数字,则跳过当前列查询下一列,若当前元素小于要查找的数,则跳过当前行查找下一行,直至找到或者找不到。

eg:

此处使用数组arr[3][3]={1,2,3,4,5,6,7,8,9};

1 2 3

4 5 6

7 8 9

在数组中朝查找5,首先判断3<5,则查找范围就变成了

4 5 6

7 8 9

再判断6>5,则查找范围又变为了

4 5

7 8

这时候再判断5=5

则找到

源代码:

#include<stdio.h>
#include<stdlib.h>
void find(int arr[][3],int *row, int *col,int key)
{
    int x = 0;
    int y = *col - 1;
    while (x <*row&&y>0)//判断条件
    {
        if (arr[x][y] == key)//找到
        {
            *row = x;
            *col = y;
            return;
        }
        else if (arr[x][y] < key)
        {
            x++;//变换行
        }
        else
        {
            y--;//变换列
        }
    }
    *row = -1;
    *col = -1;
}
int main()
{
    int arr[3][3]= {1,2,3,4,5,6,7,8,9};
    int x=3;
    int y=3;
    int *row = &x;
    int *col = &y;
    int key=5;
    find(arr,row,col,key);
    if (*row == -1 && *col == -1)
    {
        printf("没找到\n");
    }
    else
    {
        printf("找到了,下标为%d %d\n", *row, *col);
    }
    system("pause");
    return 0;
}

C语言实现在杨氏矩阵中查找数字

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2019-04/158372.htm


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

火的礼物:人类与计算技术的终极博弈(第4版)

火的礼物:人类与计算技术的终极博弈(第4版)

【美】Baase,Sara(莎拉芭氏) / 郭耀、李琦 / 电子工业出版社 / 89.00

《火的礼物:人类与计算技术的终极博弈 (第4版)》是一本讲解与计算技术相关的社会、法律和伦理问题的综合性读物。《火的礼物:人类与计算技术的终极博弈 (第4版)》以希腊神话中普罗米修斯送给人类的火的礼物作为类比,针对当前IT技术与互联网迅速发展带来的一些社会问题,从法律和道德的角度详细分析了计算机技术对隐私权、言论自由、知识产权与著作权、网络犯罪等方面带来的新的挑战和应对措施,讲解了计算技术对人类的......一起来看看 《火的礼物:人类与计算技术的终极博弈(第4版)》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器