剑指offfer：二维数组中的查找

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

例如：

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

查找7返回True，查找5返回False

-—— - —— - —— - —— - —— - —— - —— - -—— - —— - —— - —— - —— - —— - —— - -—— - —— - —— - —— - —— - —— - ——

分析：选取右上角的元素，若数字等于要查找的数字，则查找过程结束；

　　　　　　　　　　　　若大于要查找的数字，提出这个数字所在的列；

　　　　　　　　　　　　若小于则提出这个数字所在的行，每一步都可以缩小查找的范围

代码：python 2.7.3

# -*- coding:utf-8 -*-

class Solution:

    # array 二维列表

    def Find(self, target, array):

        # 标识变量

        found = False

        # 检查输入 None，空数组

        if array == None:

            return found

        nrow=len(array)-1

        ncol=len(array[0])-1

        row=0

        col=ncol

        while row<=nrow and col>=0:

            if array[row][col]==target:

                found=True

                break

            elif array[row][col]>target:

                col=col-1

            else:

                row=row+1

        return found

测试用例：1.二维数组中包含查找的数字（数组中的最大值、中间值、最小值）

2.数组中没有查找的数字（大于数组的最大值，小于数组的最小值，在数组值之间但是数组中没有这个数字）

3.特殊输入测试（输入为空）

注意：二维数组求行数为nrow=len(array)

求列数为ncol=len(array[0])

巴特西

剑指offfer：二维数组中的查找

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

最新文章

热门文章