NASA666

不以物喜,不以己悲.
Posted on , viewed 590 times

二维数组中的查找

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

解题思路
首先选取数组中右上角的数字。如果该数字等于要查找的数字,查找过程结束;如果该数字大于要查找的数字,剔除这个数字所在的列;如果该数字小于要查找的数字,剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角,则每一次都在数组的查找范围中剔除一行或者一列,这样每一步都可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空。

代码实现(golang)

package main
import (
    "fmt"
)
// 思路:
// 对于每一行,拿最后一个数和要查找的数比较,
// 若等于要查找的数,返回true,
// 如果小于要查找的数,则剔除整行,否则二分查找这行,如果找到则返回true,否则查找下一行.
const OUTER_COUNT = 10
const INNER_COUNT = 10
func main() {
    var arr [][]int
    // fmt.Println(arr)
    n := 0
    // 初始化
    for i := 0; i < OUTER_COUNT; i++ {
        sl := make([]int,0,INNER_COUNT)
        for j := 0; j < INNER_COUNT; j++ {
            sl = append(sl, n)
            n++
        }
        arr = append(arr,sl)
    }

    fmt.Println("The Array IS: ", arr)
    fmt.Println("=======================================")
    // fmt.Printf("Array Include Dest: %d ? %v\n",-1, two_dimensional_find(arr, -1))
    // fmt.Printf("Array Include Dest: %d ? %v\n",88, two_dimensional_find(arr, 88))
    // fmt.Printf("Array Include Dest: %d ? %v\n",99, two_dimensional_find(arr, 99))
    fmt.Printf("Array Include Dest: %d ? %v\n",100, two_dimensional_find(arr, 100))
    fmt.Println("=======================================")
}

func two_dimensional_find(array [][]int, dest int) (includeDest bool) {
    // fmt.Println(array)
    weigth := len(array)
    heigth := len(array[0])
    for weigth > 0 && heigth > 0 {
        tmp := array[0][heigth -1]
        if tmp == dest {
            includeDest = true
            break
        } else if tmp < dest { //删除一行
            array = array[1:weigth]
            weigth--
        } else if tmp > dest { //删除一列
            for  i := 0; i < weigth; i++ {
                array[i] = array[i][0:heigth-1]
            }
            heigth--
        }
    }
    return
}