剑指offer-二维数组中的查找

题目描述

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

输入描述

array： 待查找的二维数组 target：查找的数字

输出描述

查找到返回true，查找不到返回false

实现思路

package problem003

// 用了分治的思想，根据题意可得
// 从数组中选取数字，和目标数字的关系有三种情况：=，<或>。
// 如果是等于则查找成功；
// 如果是数组中元素小于要查找的数字，说明要查找的数字应该在当前位置的右边或下边。
// 如果是数组中元素大于要查找的数字，说明要查找的数字应该在当前位置的左边或上边。
// 即 对于数组中的任何一个元素, 比它小的元素都在它的左方或者上方, 比它大的元素都在它的右边或者下方
// 但是这两个区域还有可能有重叠，比如右边或下边会在右下角有重叠。

// 为了不重复的处理重叠的数据, 我们可以找几个特殊的起点, 比如

// 起点	 	性质							可否作为起点
// 左上角		没有上方元素(小)和左方元素(小)
// 			只有下方元素(大)和右方元素(大)		否

// 右上角		没有上方元素(小), 和右方元素(大)
// 			只有下方元素(大)和左方元素(小)		是

// 左下角		没有下方元素(大), 和左方元素(小)
// 			只有上方元素(小)和右方元素(大)		是

// 右下角		没有下方元素(大), 和右方元素(大)
// 			只有上方元素(小)和左方元素(小)		否

// 因此重叠问题的解决方法：
// 如果查找从右上角开始，如果要查找的数字不在右上角，则每次可以剔除一列或一行。
// 也可以从左下角开始
// 但是不能从左上角或者右下角开始。

func Find(board [][]int, target int) bool {
    rlen := len(board) // 行
    clen := len(board[0]) // 列
    
    // 从右上角开始查找
    for r,c := 0, clen-1; r < rlen-1 && c > 0; {
        if board[r][c] == target {
            return true
        }
        if board[r][c] > target {
            // 往左边查找
            c--
            continue
        } else {
            // 往下边查找
            r++
        }
    } 
    return false
    
    // 从左下角开始查找
    // for r,c := rlen-1, 0; r > 0 && c < clen-1; {
    //     if board[r][c] == target {
    //         return true
    //     }
    //     if board[r][c] > target {
    //         // 往上边查找
    //         r--
    //     } else {
    //         // 往右边查找
    //         c++
    //         continue
    //     }
    // }
    // return false
}

测试

package problem003
import (
    "testing"
    "github.com/stretchr/testify/assert"
)

type para struct {
    board [][]int
    target int
}

type ans struct {
    find bool
}

type question struct {
    p para
    a ans
}

func Test_OK(t *testing.T) {
    ast := assert.New(t)

    qs := []question{
        question{
            p: para{
                board: [][]int{
                    []int{ 1, 2, 8, 9, },
                    []int{ 2, 4, 9, 12, },
                    []int{ 4, 7, 10, 13, },
                    []int{ 6, 8, 11, 15, },	
                },
                target: 7,
            },
            a: ans{
                find: true,
            },
        },
        question{
            p: para{
                board: [][]int{
                    []int{ 1, 2, 8, 9, },
                    []int{ 2, 4, 9, 12, },
                    []int{ 4, 6, 10, 13, },
                    []int{ 6, 8, 11, 15, },		
                },
                target: 7,
            },
            a: ans{
                find: false,
            },
        },
    }

    for _, q := range qs {
        a, p := q.a, q.p
        ast.Equal(a.find, Find(p.board, p.target), "输入:%v", p)
    }
}