剑指Offer - PHP二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
分析
已知：行从左到右递增，列从上到下递增。
初始：数组初始查找位置位于左下角（即最后一行的第一个元素）
查找：如果 target（目标数）小于当前数组元素，说明要往上一行查找（因为右边是比它大的）；如果 target 大于当前数组元素，说明要往当前行的右边查找。
代码
public function test()
{
$array = [[1, 2, 8, 9], [2, 4, 9, 12], [4, 7, 10, 13], [6, 8, 11, 15]];
$target = 7;
$arr_num = count($array); // 计算子数组个数
$element_num = count($array[0]); // 计算每个子数组的元素个数
// 从数组的最后一个子数组的第一个元素开始
$i = $arr_num - 1;
$j = 0;
while ($i >= 0 && $j < $element_num) {
// 如果目标数等于当前数，返回 true
if ($target == $array[$i][$j]) {
return true;
} elseif ($target < $array[$i][$j]) {
// 如果目标数小于当前数，往上一行走
$i--;
} else {
// 如果目标数大于当前数，往当前行的右边走
$j++;
}
}
// 没找到，返回 false
return false;
}
关于 LearnKu
粤公网安备 44030502004330号