题目

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

思路

实例1

使用实例举例子比如下面的矩阵中查找 1

1 2 3 4
2 3 4 5
3 4 5 6
6 7 8 9

如果我们从右上角的 4 开始比较

因为 右上角是一行的最大值和一列的最小值, 如果 target < 右上角, 那么就能排除一列,如果 target > 右上角就能排除一行

(1) 1 < 4 排除一列

1 2 3
2 3 4 
3 4 5 
6 7 8 

(2) 1 < 3 排除一列

1 2 
2 3 
3 4 
6 7 

(3) 1 < 2 排除一列

1 
2 
3 
6 

(4) 1 == 1 命中, 返回 true

实例2

使用实例举例子比如下面的矩阵中查找 7

1 2 3 4
2 3 4 5
3 4 5 6
6 7 8 9

如果我们从右上角的 4 开始比较

因为 右上角是一行的最大值和一列的最小值, 如果 target < 右上角, 那么就能排除一列,如果 target > 右上角就能排除一行

(1) 7 > 4 排除一行

2 3 4 5
3 4 5 6
6 7 8 9

(2) 7 > 5 排除一行

3 4 5 6
6 7 8 9

(3) 7 > 6 排除一行

6 7 8 9

(4) 7<9 排除一列

6 7 8 

(5) 7<8 排除一列

6 7 

(6) 7 == 7 命中

golang 代码

//判断整数在有序的二维数组(左到右,上到下递增)中是否存在
func Exists(matrix [][]int, target int) (exists bool) {
	//参数处理
	if len(matrix) == 0 {
		return
	}
	//todo: 保证每个 row 的元素都是一致的, 保证这是一个矩形
	//右上角的坐标
	x := 0
	y := len(matrix[0]) - 1
	for {
		//溢出旧退出没有命中
		if y == -1 || x == len(matrix) {
			return
		}
		//命中
		if matrix[x][y] == target {
			return true
		}
		//小于 target 减少行 ,
		if matrix[x][y] < target {
			x++
			continue
		}
		//大于 target 减少列
		if matrix[x][y] > target {
			y--
			continue
		}
	}
}

测试用例1

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)
func TestP3(t *testing.T) {
	testDatas := []struct {
		marix  [][]int
		target int
		except bool
	}{
		{
			marix: [][]int{
				{1, 2, 3, 4},
				{2, 3, 4, 5},
				{3, 4, 5, 6},
				{6, 7, 8, 9},
			},
			target: 7,
			except: true,
		},
	}
	for _, testData := range testDatas {
		assert.Equal(t, testData.except, Exists(testData.marix, testData.target))
	}
}