专栏首页陌无崖知识分享Go快速查找有序二维数组的数字

Go快速查找有序二维数组的数字

作者 | 陌无崖

转载请联系授权

导语

大家肯定对数组都不陌生,今天的这道题就是关于数组的,在做这道题之前呢,先带领大家回顾一下数组的要点。

数组

数组是一块连续的内存并按照顺序存储数据,使用数组必须分配内存,因此数组的空间效率差,经常会出现空闲的区域没有得到充分利用。数组的的内存连续,根据下标在O(1)时间读/写任何元素,时间效率高。

题目描述

在一个二维数组中,每一行都按照从左到右的递增顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数输入这样的一个二维数组和整数,判断该整数是否在该二维数组中。如:

1  2  8  9
2  4  9  12
4  7  10 13
6  8  11 15

解决思路

对于这样的题,我们应该尽量利用该类数组的性质,根据数组已经排好的序列,很明显我们应该在比较的过程中,不断缩小比较的区域,通常的我们的思路是从1开始比较,我们可以尝试一下,比如我们找7这个数字,1比7小,因此,7应该在1的下面或右边,这个时候出现了问题,们是因该比较右边的还是下面呢?因此这个思路不行,那如果我们从顶点9开始呢,发现9比7大,那7一定在9的右边,因此我们可以比较8,发现仍然比较大,因此我们比较2,发现比7小,那么一定在下面,因此开始比较4,然后比较7,最终找到。很明显这个思路比较容易。按照这个思路大家可以在自己的草稿纸上进行画图尝试一下。找一下规律,暂时先不要看下面的部分。

规律

通过以上的思路我们可以发现如下规律

a[i][j] > num 时,j--
a[i][j] < num 时,i++

代码

找到了以上规律我们就可以轻松的完成我们的代码设计了

type S1 []int
type S2 []S1

func FindNum(data S2, row, col, num int) bool {
  if len(data) == 0 || row <= 0 || col <= 0 {
    return false
  }
  //
  i := 0
  j := col - 1
  for {
    if i < 0 || j < 0 {
      break
    }
    if data[i][j] > num {
      j--
    } else if data[i][j] < num {
      i++
    } else {
      return true
    }
  }
  return false
}

这里需要注意的是为了满足传入各种数组的要求,在定义二维数组时使用了下面的方式

type S1 []int
type S2 []S1

单元测试案例

为了保证我们的代码时成功的你也可以使用以下测试案例,或者自写案例

demo1是我传入的自定义的包

func TestFindNum(t *testing.T) {
  // 定义一个完整数组
  // var data [][4]int
  // data = make([][4]int, 4)
  // fmt.Println(data)[[0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0]]
  // 初始化二维数组
  fmt.Println("测试用例1******")
  a := demo1.S2{
    demo1.S1{1, 2, 8, 9},
    demo1.S1{2, 4, 9, 12},
    demo1.S1{4, 7, 10, 13},
    demo1.S1{6, 8, 11, 15},
  }
  num1, num2 := 8, 3
  if demo1.FindNum(a, 4, 4, num1) == true && demo1.FindNum(a, 4, 4, num2) == false {
    fmt.Println("success")
  } else {
    fmt.Println("fail")
  }
  fmt.Println("测试用例2********")
  a = demo1.S2{}
  if demo1.FindNum(a, 4, 4, num1) == false {
    fmt.Println("success")
  } else {
    fmt.Println("fail")
  }
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 有序数组中查找具体数字n(二分查找)

       我们先定义一个有序的数组arr,再设置数组中的一个数字k为我们所寻找的值,当数字与算法结果匹配时,打印“找到了,下标为–”,若该数字在数组中未查找到,则打...

    RAIN7
  • 二维数组的查找

    题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否...

    猿人谷
  • [剑指offer] 二维数组中的查找

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

    尾尾部落
  • 003-二维数组的查找

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

    单车变摩托
  • 二维数组中的查找

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

    用户3003813
  • [剑指]1二维数组的查找

    这里用两种方法解决,第一种是前面说解题思路,第二种则是普遍的解题思路,两者的时间复杂度不同。

    程序员的时光001
  • 二维数组中的查找

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M 热度指数:1946753

    后端码匠
  • LeetCode120|二维数组中的查找

    在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断...

    码农王同学
  • 二维数组中的查找代码

    desperate633
  • 算法-二维数组中的查找

    问题: 在一个二维数组中,每一行元素都按照从左到右递增的顺序排序,每一列元素都按照从上到下递增的顺序排序。实现一个查找功能的函数,函数的输入为二维数组和一个...

    chaibubble
  • 牛客网-二维数组的查找

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

    TrueDei
  • 有序数组中与任意数组查找不同的部分-二分查找

    sr
  • 剑指Offer-二维数组中的查找

    package Array; /** * 二维数组中的查找 * 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。...

    武培轩
  • 剑指offer:二维数组中的查找

    一种简单的方法就是整个数组都遍历,当然,数组从左到右,从上到下都是有序的,如果你遍历整个数组的话,那就浪费了数组的局部有序性了。

    帅地
  • 【剑指offer】二维数组中的查找

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 剑指offer--二维数组中的查找

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

    AI那点小事
  • 剑指offer__4__二维数组中的查找

    描述:在一个二维数组中,每一行都按照从左到右的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一函数,输入这样的一个二维数组,和一个数,判断数组中是否含有该...

    用户6055494
  • 二分查找搜索局部有序数组

    升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。

    MickyInvQ
  • 查找算法:在双重排序的数组中进行快速查找

    假设A是一个n\*n的二维数组。它的行和列都按照升序排列,给定一个数值x,设计一个有效算法,能快速在数组A中查找x是否存在。同时考虑一个算法效率的下界,也就是无...

    望月从良

扫码关注云+社区

领取腾讯云代金券