DIV CSS 佈局教程網

楊氏矩陣查找的 JS 實現代碼
編輯:關於JavaScript     

楊氏矩陣是一種特殊的矩陣:每一行從左到右遞增,每一列從上到下遞增。在這種矩陣中查找特定數字,是資料結構與演算法中的經典問題。以下示範如何用 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),這也是它相較於暴力遍歷的優勢所在。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved