剑指Offer（Python）二维数组中的查找

Created2017-10-10Updated2021-03-21

推荐在线编程平台

牛客网在线编程

题目描述

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

分析

由题意我们可以知道，该二维数组最左上角的元素最小，最右下角的元素最大，所以我们可以先判断目标值与这两个元素的大小。这里有两种情况我们可以分别考虑：

  • 目标超过这两个元素的范围
    如果目标小于数组最小值或者大于最大值，那么我们就可以判断出它不在二维数组里面。

  • 目标在两个元素之间
    当目标元素在两个值之间的时候，我们可以对二维数组进行遍历，判断每一层的元素：如果目标元素比该层第一个小或者比最后一个元素大，则说明不在该层，直接跳过。如果目标元素在该层范围里面，则遍历该层，如果没有元素与之匹配则说明该二维数组不包含目标值。

代码

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if (array == None or len(array) == 0):
            return 0

        for x in array:
            if (x == None or len(x) == 0):
                return 0

            if (x[0] > target and x[len(x) - 1] < target):
                break

            for y in x:
                if (y == target):
                    return 1

        return 0

也可以直接用两个for循环判断每一个元素与目标的值

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        for x in array:
            for y in x:
                if (y == target):
                    return 1
        return 0
Search by:GoogleBingBaidu