二维数组中的查找

发表于

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

1
2
3
4
5
6
[
    [1,2,8,9],
    [2,4,9,12],
    [4,7,10,13],
    [6,8,11,15]
]

给定 target = 7，返回 true。
给定 target = 3，返回 false。

数据范围： 矩阵的长宽满足0≤n,m≤500，矩阵中的值满足0≤val≤109
要求： 空间复杂度O(1)，时间复杂度O(n+m)

示例1

1
2
3
输入:  7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回:  true
说明:  存在7，返回true

示例2

1
2
输入:  1,[[2]]
返回:  false

示例3

1
2
3
输入:  3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回:  false
说明:  不存在3，返回false

题解

每一列都是按照从上到下递增的顺序排序，那么直接用每一列的开始和结尾和target比较，如果target在区间内，就遍历该列，找到target就返回true，否则返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package main

/**
 * 
 * @param target int整型 
 * @param array int整型二维数组 
 * @return bool布尔型
*/
func Find( target int ,  array [][]int ) bool {
    // write code here
    rows := len(array)
    if rows == 0 {
        return false
    }
    j := len(array[0]) - 1
    i := 0
    // todo: 遍历区间时是暴力遍历,可以修改为二分查找
    for i < rows && j >= 0 {
        v := array[i][j]
        if v > target {
            j--
        } else if v < target {
            i++
        } else {
            return true
        }
    }

    return false

}