前端算法題：二維數組中（每個一維數組的長度相同），左右和上下分別遞增，求是否含有指定整數

CocoaChina 發布于2019-08-23 14:49 / 1925人閱讀

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

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

我們先假設一個二維數組列出來，形成一個矩陣，便于我們的理解

[10, 20, 40, 60], 
[20, 30, 70, 90], 
[40, 50, 80, 110],

根據題意我們可以得到如下理論：

①最小數（min）是第一行第一個，最大數（max）是最后一行的最后一個
②每一行最大的一個數是每一行的最后一個，每一行最小一個數是每一行的第一個

根據第一個結論我們就可以先判斷這個數是否在這個矩陣內

let min = array[0][0]
let max = array[array.length-1][array[0].length-1]
if (target < min || target > max)?
    return false

接下來，我們就根據第二個條件來查找：思路如下

先從第一行的最后一個數（稱為J），開始比較，如果目標大于J，則與下一行的最后一個數比較，如此循環，直到目標比J小

當目標比J小時，我們就能確定是哪一行，之后你懂得，代碼如下

function Find(target, array) {
            
    let i = 0
    let j = array[i].length - 1
    let min = array[0][0]
    let max = array[array.length-1][array[0].length-1]
 
    if (target < min || target > max) 
        return false
                    
    while (i < array.length && j >= 0) {
        if (array[i][j] < target) {
            i++
        } else if (array[i][j] > target) {
            j--
        } else {
            return true
        }
    }
    return false
}

GPU云服務器云服務器 java中二維數組的長度一維數組和二維數組 python一維數組和二維數組 java中二維數組長度

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

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

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

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

Worktile 2019-08-23 10:22 評論0 收藏0
Union-Find并查集算法學習筆記

摘要：算法鏈接學習工具，，環境搭建在小伙伴的推薦下，這個學期開始上普林斯頓的算法課。一系列的整數對代表與相互連接，比如等，每一個整數代表了一個。我覺得這個可能也是并查集相關應用。這學期繼續學習深入理解了就能明白了。《算法》鏈接：1.5 Case Study: Union-Find學習工具：mac，java8，eclipse,coursera 環境搭建在小伙伴的推薦下，這個學期開始上普林斯頓...

hzc 2019-08-14 17:08 評論0 收藏0
【劍指offer】1.二維數組查找

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

wawor4827 2019-08-23 14:32 評論0 收藏0
劍指offer中的算法題(PHP版)

摘要：二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計算的時間復雜度是以的指數的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。二維數組中的查找在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和...

big_cat 2019-06-27 15:43 評論0 收藏0
【數據科學系統學習】Python # 數據分析基本操作[一] numpy

摘要：提供了使我們能夠快速便捷地處理結構化數據的大量數據結構和函數。結構化數據，例如多維數據矩陣表格行數據，其中各列可能是不同的類型字符串數值日期等。基礎數組和矢量計算高性能科學計算和數據分析的基礎包。本篇內容為整理《利用Python進行數據分析》，博主使用代碼為 Python3，部分內容和書本有出入。利用 Python 進行科學計算的實用指南。本書重點介紹了用于高效解決各種數據分析問...

wushuiyong 2019-07-31 11:11 評論0 收藏0