[剑指-01](php&python):二维数组中的查找

说明：记录刷剑指offer，使用php与python两种语言，对解题思路以及涉及到的基本语法以及知识点做学习记录。其中对于每道题目进行粗略的分类。

题目来源

分类：数组
二维数组中的查找

题目描述

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

解题思路（参考剑指offer 第二版）

举例：下面的二维数组每行，每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找5，则返回fasle。

剑指offer例子
具体解题过程
Note：利用二维数组是特殊的性（从左向右增，从上到下增）剑指offer采用选取右上角的数字，在这里可以使用选取与此同理的方法，选择从左下角开始。但不能选择左上角和右下角的数字，这种选取方式无法缩小查找的范围。

具体解题过程
a. 选取数组中右上角的数字
b. 进行判断：1.如果该数字等于要查找的数字，则查找结束；2.如果该数字大于要查找的数组，则剔除这个数字所在列；3.如果该数字小于要查找的数字，剔除这个数字所在的行。总体来说，如果要查找的数字不在数组的右上角，则每一次在数组的查找范围中剔除一行或者一列，这样就可以缩小查找范围，直到找到要查找的数字，或者查找范围为空。

编程实现

PHP

运行时间：486ms

占用内存：3808k
<?php

function Find($target, $array)
{
    //获得行，列数
    $rows = count($array);
    $cols = count($array[0]);
    if (!empty($array) && $rows > 0 && $cols > 0) {
        $row = 0;
        $col = $cols - 1;
        while ($row < $rows && $col >= 0) {
            /* a. 如果该数字大于要查找的数组，则剔除这个数字所在列;
               b. 如果该数字小于要查找的数字，剔除这个数字所在的行;
               c. 如果该数字等于要查找的数字，则查找结束*/
            if ($array[$row][$col] > $target) {
                $col -= 1;
            } elseif ($array[$row][$col] < $target) {
                $row += 1;
            } else {
                return True;
            }
        }
    }
    return false;
}
/* 测试用例 
a. 二维数组包含找到的target（查找最大值/最小值/最大值-最小值之间包含的值）
b. 二维数组不包含找到的target（查找大于最大/小于最小/不在最大与最小之间）
c.特殊输入测试（数组为空等）

*/
$array = array(array(1,2,8,9),array(2,4,9,12),array(4,7,10,13),array(6,8,11,15),array(9,10,12,17));
$target = 18;
var_dump(Find($array, $target));
?>

Python

运行时间：373ms

占用内存：5628k
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array:
            return False
        rows = len(array)
        cols = len(array[0])
        
        row = 0
        col = cols - 1
        while row < rows and col >= 0:
            if array[row][col] > target:
                col -= 1
            elif array[row][col] < target:
                row += 1
            else:
                return True
        return False
if __name__ == "__main__":
    array = [[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
    target = 7
    S = Solution()
    if S.Find(target, array):
        print("OK!")
    else:
        print("Not Found!")

知识总结复习

PHP数组的声明（一维/多维）
array(array(),array())
布尔类型
参考学习：http://www.cnblogs.com/xielong/p/9874955.html
PHP不区分大小写， Python区别（返回True/False）
python __name__=='__mian__' 理解
if _name_ == '_main_'的意思是：当.py文件被直接运行时，if _name_ == '_main_'之下的代码块将被运行；当.py文件以模块形式被导入时，if _name_ == '_main_'之下的代码块不被运行。
参考学习：https://www.cnblogs.com/GGGGGGZX/p/9206806.html

最后编辑于：2018.12.25 16:41:16