行元素從小到大遞增,列元素從小到大遞增的數組查找演算法

WBOY
發布: 2016-08-08 09:22:04
原創
1129 人瀏覽過

題目:在一個二維數組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組是否含有該整數。

考點:這題主要是要利用好所給的兩個條件,行遞增和列遞增,將肯定不合適的數據排除在外,將要遍歷的數據盡可能的減少。

數組範例如下:

121011
1 2 24
12 4 7
13 6 8
15 15

15

通過觀察可知,

1.列最開頭如果大於要查找的數,那麼要查找的數不可能在那一列,可以直接剪枝掉那一列;

結果如下: 124發現,行最末尾的數如果小於要找的數,那麼要找的數字肯定也不在那一行;結果如下:
2
4
7

4

7資料就剪成最少的可能的數量,然後再對這些資料進行遍歷查找,就可以了。 程式碼如下:
<?php
/*
$data  数组
$number 查找的数
$rows 数组的行数
$columns 数组的列数
*/
function inArray($data,$number,$rows,$columns)
{
	$row=0;
	$column=$columns-1;
	$first=true;
	while($row<$rows&&$column>=0)
	{
		if($data[$row][$column]>$number&&$first)
		{
			$column--;
			//echo $column.',';
		}
		if($data[$row][$column]<$number)
		{
			$first=false;
			$row++;
			//echo $row.&#39;,&#39;;
			//如果查找的数大于数组中的所有元素,那么就遍历完所有的行后退出
			//continue是防止这种情况的出现,会和第四个条件冲突
			continue;
		}
		if($data[$row][$column]==$number)
		{
			return true;
		}
		if($data[$row][$column]>$number&&!$first)
		{
			break;
		}
	}

	for($i=$row;$i<$rows;$i++)
	{
		for($j=0;$j<$column;$j++)
		{
			if($data[$i][$j]==$number)
			{
				return true;
			}
		}
	}
	return false;
}

$a=array(array(1,2,8,9),array(2,4,9,12),array(4,7,10,13),array(6,8,11,15));
var_dump(inArray($a,7,4,4));
var_dump(inArray($a,101,4,4));
登入後複製
版權聲明:本文為部落客原創文章,未經部落客允許不得轉載。 以上就介紹了行元素從小到大遞增,列元素從小到大遞增的數組查找演算法,包括了方面的內容,希望對PHP教程有興趣的朋友有所幫助。
相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板