题目地址: 二维数组中的查找

题目描述

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

思路

数组是个有序矩阵,其格式如下,对其中位数而言(图中红色字体),其左上方为小于该数,右下方为大于该数

image.png

因此,考虑的一种查找方式为,从中位数开始进行判断,若数比目标值小,则查找坐标向左上部移动,反之向右下部移动,具体移动的时候要考虑是否触及了边界,以左上部移动为例,如下图,假设红色为当前值所在区域,然后判断向1方块是否能移动,并且该方块未遍历过,若能则向之移动,否则向2方块移动,经过同样的判断,若不能移动则向3方块移动,若判断还是不通过,则认为数组中无匹配的数字.

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        
        # 图像宽高
        w, h = len(array[0]), len(array)
        # 中位数坐标
        center_y, center_x = h // 2, w // 2
        
        # 遍历
        while True:
            
            # 判断坐标是否有越界,若有则返回False
            if center_x < 0 or center_x >= w:
                return False
            if center_y < 0 or center_y >= h:
                return False
            
            # 判断该坐标是否已经搜索过,若是则退出(已经搜索过的需要将值标记为"a")
            if array[center_y][center_x] == "a":
                return False
            
            # 缓存当前坐标
            x, y = center_x, center_y
            
            if array[center_y][center_x] == target:
                # 匹配成功
                return True
            elif array[center_y][center_x] > target:
                # 当前值比目标值大,因此需要向左半部移动
                
                # 详判断能否向方块1处移动
                if center_y > 0 and center_x > 0:
                    if array[center_y - 1][center_x - 1] != "a":
                        center_x, center_y = center_x - 1, center_y - 1
                        
                        # 标记为已搜索
                        array[y][x] = "a"
                        continue

                # 详判断能否向方块2处移动
                if center_y > 0 and array[center_y - 1][center_x] != "a":
                    center_y -= 1
                    array[y][x] = "a"
                    continue

                # 详判断能否向方块3处移动
                if center_x > 0 and array[center_y][center_x - 1] != "a":
                    center_x -= 1
                    array[y][x] = "a"
                    continue
                
                # 不可移动,返回无搜索结果
                return False
            else:
                if center_y < h - 1 and center_x < w - 1:
                    if array[center_y + 1][center_x + 1] != "a":
                        center_x, center_y = center_x + 1, center_y + 1
                        array[y][x] = "a"
                        continue
                if center_y < h - 1 and array[center_y + 1][center_x] != "a":
                    center_y += 1
                    array[y][x] = "a"
                    continue

                if center_x < w - 1 and array[center_y][center_x + 1] != "a":
                    center_x += 1
                    array[y][x] = "a"
                    continue

                return False