楊氏矩陣是一種特殊的矩陣:每一行從左到右遞增,每一列從上到下遞增。在這種矩陣中查找特定數字,是資料結構與演算法中的經典問題。以下示範如何用 JavaScript 實現楊氏矩陣的構造與查找。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="https://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />
<title>楊氏矩陣查找</title>
</head>
<body>
<script language="javascript">
function xunhuan()
{
var m = parseInt(document.getElementsByTagName("input")[0].value) || document.getElementsByTagName("input")[0].getAttribute("value");
var n = parseInt(document.getElementsByTagName("input")[1].value) || document.getElementsByTagName("input")[1].getAttribute("value");
var t = parseInt(document.getElementsByTagName("input")[2].value) || document.getElementsByTagName("input")[2].getAttribute("value");
if(m >= 1 && n <= 1000 && t >= 1 && t <= 1000000)
{
var num = 2;
for(var x = 0; x < m; x++)
{
for(var y = 0; y < n; y++)
{
document.write((num++) + " ");
}
document.write("<br/>");
}
var a = new Array();
for(var e = m*n+1; e > 1; e--)
{
a.splice(0, 0, e)
}
chazhao(a, t);
}
else
{
alert("不符合要求,請重新輸入");
}
}
function chazhao(a, number)
{
document.write(isCon(a, number));
function isCon(a, number)
{
for(var i=0; i<a.length; i++)
{
if(a[i] === number)
{
return String(true);
}
}
return String(false);
}
}
</script>
<form>
<p>矩陣行數:<input type="text" name="矩陣行數" value=3 /> 矩陣列數:<input type="text" name="矩陣列數" value=3 /></p>
<p>查詢數字:<input type="text" name="查詢數字" value=1 /></p>
<input type="button" onclick="xunhuan()" value="數組" />
</form>
</body>
</html>
這個範例透過輸入矩陣的行列數與查詢數字,先構造出符合楊氏矩陣特性的資料,再進行查找並輸出結果。實際應用中,楊氏矩陣的高效查找通常從右上角(或左下角)開始,根據比較結果逐步排除一整行或一整列,將時間複雜度控制在 O(m+n),這也是它相較於暴力遍歷的優勢所在。