leetcode剑指 Offer 04. 二维数组中的查找

leetcode

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

二分查找法\

1. 遇到这种有序的数据查找通常会想到二分查找,就是找不断查找数据的1/2数据的大小从而不断缩小查找的范围,找到数据

//二分查找数据
func findnum(a []int, t int) bool {
 if len(a) == 0 {
  return false
 }
 i := len(a) / 2
 if a[i] == t {
  return true
 } else if i == 0 {//只剩下小于2(不包含)个数据,且不相同返回false
  return false
 } else if a[i] < t {
  return findnum(a[i:], t)
 } else {
  return findnum(a[:i], t)
 }
}

• 时间复杂度(O(n * log n))
• 空间复杂度(O(log n))
  其中 n 为 a 数组的长度。findnum 函数是一个递归函数，它在每次递归调用时只需要存储一个中间变量 i，并且每次递归调用的 a 数组长度都会缩小一半，因此递归树的高度最多为 log n。

执行结果

法1

func findnum(a []int, t int) bool {
 if len(a) == 0 {
  return false
 }
 i := len(a) / 2
 if a[i] == t {
  return true
 } else if i == 0 {
  return false
 } else if a[i] < t {
  return findnum(a[i:], t)
 } else {
  return findnum(a[:i], t)
 }
}
func findNumberIn2DArray(matrix [][]int, target int) bool {
 for _, v := range matrix {
  if findnum(v, target) {
   return true
  }
 }
 return false
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 20 ms , 在所有 Go 提交中击败了 77.77% 的用户 内存消耗： 6.6 MB , 在所有 Go 提交中击败了 49.07% 的用户 通过测试用例： 129 / 129