说明：记录刷剑指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
网友评论