【刷算法】二維數組中的查找

Worktile 發布于2019-08-23 10:22 / 2935人閱讀

摘要：題目描述在一個二維數組中每個一維數組的長度相同，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。分析例如二維數組，，如果按照常規的查找，從開始，那么，和都大于，接下來該怎么辦呢這就陷入了一個無法進行下去的局面。

題目描述

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

分析

例如二維數組arr = [

[1,2,3,4],
[5,6,7,8],
[9,10,11,12]

]，target=7，如果按照常規的查找，從arr0開始，那么target>arr0，arr0和arr1都大于arr0，接下來該怎么辦呢？這就陷入了一個無法進行下去的局面。

所以，要在一個數組中查找某target，則有辦法確定一個唯一的方向，即下一步該向左還是向右、向上還是向下。

觀察題目，二維數組的每一行都按照從左向右遞增，每一列都按照從上到下遞增，那么如果從二維數組的左下角開始，就可以保證向上的都是小的，向右的都是大的，過程就可以進行下去了。

代碼實現

function Find(target, array)
{
    if(array === null)
        return false;
    var curRow = array.length-1;
    var curCol = 0;

    while(curRow >=0 && curCol < array[0].length){
        if(array[curRow][curCol] === target)
            return true;
        else if(array[curRow][curCol] > target)
            curRow--;
        else 
            curCol++
    }

    return false;
}

GPU云服務器云服務器 javascript中的二維數組 java中的二維數組 python中的二維數組找出一個二維數組中的鞍點

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/96278.html

【前端來刷LeetCode】兩數之和與兩數相加

摘要：給定表，存在函數，對任意給定的關鍵字值，代入函數后若能得到包含該關鍵字的記錄在表中的地址，則稱表為哈希表，函數為哈希函數。而中的對象就是基于哈希表結構，所以我們構造一個對象即可，是當前遍歷到的值，是其與目標值的差。大部分玩前端的小伙伴，在算法上都相對要薄弱些，畢竟調樣式、調兼容就夠掉頭發的了，哪還有多余的頭發再去折騰。確實在前端中需要使用到算法的地方是比較少，但若要往高級方向發展，...

BLUE 2019-08-26 13:53 評論0 收藏0
每日一道算法題--二維數組中的查找--python

摘要：題目描述代碼思路思路一按行執行二分查找，只要該行的第一個元素小于目標，就對該行二分查找。思路二從數組的左下角開始查找，如果當前值小于目標，就向右，即如果當前值大于目標，就向上，即。【題目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/22/16addf094e0320ca); 【代碼思路】思路一：按行執行二分查找，只要該行的第一個元素小于目...

番茄西紅柿 2019-05-23 16:08 評論0 收藏0
每日一道算法題--二維數組中的查找--python

摘要：題目描述代碼思路思路一按行執行二分查找，只要該行的第一個元素小于目標，就對該行二分查找。思路二從數組的左下角開始查找，如果當前值小于目標，就向右，即如果當前值大于目標，就向上，即。【題目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/22/16addf094e0320ca); 【代碼思路】思路一：按行執行二分查找，只要該行的第一個元素小于目...

luck 2019-05-23 11:56 評論0 收藏0