二维数组中的查找

1. 题目描述

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

2. 思路

• 暴力法：遍历每个元素判断是否相等
• 从右上往左下找
  • 

3. 实现

3.1. 暴力法

// 暴力求解 
// 时间：O(mn)
// 空间：O(1)
func Find(target int, array [][]int) bool {
	for _, row := range array {
		for _, col := range row {
			if col == target {
				return true
			}
		}
	}

	return false
}

3.2. 从右上往左下找

// 从右上角往左下角找
// 1,2,8,9
// 2,4,9,12
// 4,7,10,13
// 6,8,11,15
// 时间：O(m+n)
// 空间：O(1)
func Find2(target int, array [][]int) bool {
	if len(array) == 0 || len(array[0]) == 0 {
		return false
	}

	rowBound := len(array) - 1
	colBound := len(array[0]) - 1

	row := 0
	col := colBound
	for row <= rowBound && col >= 0 {
		if array[row][col] == target {
			return true
		} else if array[row][col] < target {
			row++
		} else {
			col--
		}

	}

	return false
}

4. 参考

• 二维数组中的查找_牛客网
• LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCode）