当前位置:首页 » 《资源分享》 » 正文

剑指offer 04.二维数组中的查找 我妹妹都看的懂的方法_guankunkunwd的博客

10 人参与  2021年10月21日 07:04  分类 : 《资源分享》  评论

点击全文阅读


在这里插入图片描述

欢迎来到剑指offer好题精选专栏,一起学习,一起进步

题目信息:

在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

要求:时间复杂度O(n),空间复杂度O(1)
难度:中等

示例二维数组如下: 需要找的数字: 9
int [][]array = {
{1,2,8,9},
{2,4,9,12},
{4,7,10,13},
{6,8,11,15}
};

返回TRUE


解题思路:

假设target是要找的数,因为该二维数组满足,从上到下,从左到右依次递增的规律。也就是说又靠右右靠下的数是越来越大的。从二维数组的 第一行最后一列开始(最右上角的那个数)和target比较,如果大了,将列减小一列,如果小了,将行增加一行。直到找到该数字。

从下面这个图来一起试一遍把⭐

1、num=9,target=10。num小于target,将行增加一行。

在这里插入图片描述

2、num=12,target=10,num>target。将列缩减一行。
在这里插入图片描述
3、num=9,target=10,num<target将行增加一行。

在这里插入图片描述
4、num=10、target=10 找到了!
在这里插入图片描述


代码如下:

C语言版:

bool Find(int* matrix, int rows, int cols, int number){
bool find = false;
if (matrix != NULL && rows > 0 && cols > 0){
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0){
//1:第一次尝试数组右上角那个数字和number是否匹配
if (matrix[row * cols + col] == number){
find = true;
break;
}
//2:  如果数组中的数字大于number,就说明number应该在这个数字的左边,自己那一列不包含要查找的数字
else if (matrix[row * cols + col] > number){
--col;
}
//3:  如果数组中的数组小于number,就说明number应该在它的下边,自己那一行不包含要查找的数字
 else{
 ++row
 }
 }
 }
 return find;
 }

JAVA版:

public class Solution {
    public boolean Find(int target, int [][] array) {
         if(array==null ||array.length==0 ||array[0].length==0){
             return false;
         }
        int rows=array.length;
        int cols=array[0].length;
        int row=0;
        int col=array[0].length-1;       
        while(row<rows && col>=0){
            int num=array[row][col];
            if(num==target){
                return true;
            }
         else   if(num>target){
                --col;
            }
            else if(num<target){
                ++row;
            }
        }
          return false;
        }
  
    }

你学会了吗?
在这里插入图片描述


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/30053.html

数组  数字  递增  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 全文缘来是你早注定良心(萧千雅胡一阳)列表_全文缘来是你早注定良心
  • 「爱让我溺毙而亡」小说节选推荐_[羽柔乔羽柔林絮]章节限时抢先看‌
  • 此去经年人未还霍沉洲沈青禾后续结局霍沉洲
  • 山海不相逢内容精选(温逸尘沈衿)_山海不相逢内容精选(温逸尘沈衿)
  • (番外)+(全书)霍沉洲沈青禾此去经年人未还(霍沉洲沈青禾)_(霍沉洲沈青禾此去经年人未还)列表_笔趣阁(霍沉洲沈青禾)
  • (番外)+(全书)霍沉洲沈青禾(此去经年人未还霍沉洲沈青禾)完结_(霍沉洲沈青禾)列表_笔趣阁(此去经年人未还霍沉洲沈青禾)
  • 「重回八零,拒绝替嫁冲喜」章节彩蛋限时释出‌_卫东玉兰苏夏人气小说未删减节选
  • 重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费重生七零祁同伟不再是农民儿子结局+番外纯净版全书免费
  • 傅雅宁的神女老婆,却在背地承欢作乐顾尘傅雅宁全书在线
  • 全文神女老婆,却在背地承欢作乐全局(顾尘傅雅宁)列表_全文神女老婆,却在背地承欢作乐全局
  • (番外)+(全书)此去经年人未还全书+番外+后续免费下载_(沈青禾霍沉洲)此去经年人未还全书+番外+后续列表_笔趣阁(沈青禾霍沉洲)
  • 完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续列表_完结文毁容的姐姐和瞎眼的我离开后,姜家两兄弟悔哭了+后续(林梦婉)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1