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

CocoaChina 發(fā)布于2019-08-23 14:49 / 1934人閱讀

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

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

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

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

根據(jù)題意我們可以得到如下理論：

①最小數(shù)（min）是第一行第一個(gè)，最大數(shù)（max）是最后一行的最后一個(gè)
②每一行最大的一個(gè)數(shù)是每一行的最后一個(gè)，每一行最小一個(gè)數(shù)是每一行的第一個(gè)

根據(jù)第一個(gè)結(jié)論我們就可以先判斷這個(gè)數(shù)是否在這個(gè)矩陣內(nèi)

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

接下來，我們就根據(jù)第二個(gè)條件來查找：思路如下

先從第一行的最后一個(gè)數(shù)（稱為J），開始比較，如果目標(biāo)大于J，則與下一行的最后一個(gè)數(shù)比較，如此循環(huán)，直到目標(biāo)比J小

當(dāng)目標(biāo)比J小時(shí)，我們就能確定是哪一行，之后你懂得，代碼如下

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云服務(wù)器云服務(wù)器 java中二維數(shù)組的長(zhǎng)度一維數(shù)組和二維數(shù)組 python一維數(shù)組和二維數(shù)組 java中二維數(shù)組長(zhǎng)度

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/101191.html

相關(guān)文章

【刷算法】二維數(shù)組中的查找

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

Worktile 2019-08-23 10:22 評(píng)論0 收藏0
Union-Find并查集算法學(xué)習(xí)筆記

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

hzc 2019-08-14 17:08 評(píng)論0 收藏0
【劍指offer】1.二維數(shù)組查找

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

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

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

big_cat 2019-06-27 15:43 評(píng)論0 收藏0
【數(shù)據(jù)科學(xué)系統(tǒng)學(xué)習(xí)】Python # 數(shù)據(jù)分析基本操作[一] numpy

摘要：提供了使我們能夠快速便捷地處理結(jié)構(gòu)化數(shù)據(jù)的大量數(shù)據(jù)結(jié)構(gòu)和函數(shù)。結(jié)構(gòu)化數(shù)據(jù)，例如多維數(shù)據(jù)矩陣表格行數(shù)據(jù)，其中各列可能是不同的類型字符串?dāng)?shù)值日期等?；A(chǔ)數(shù)組和矢量計(jì)算高性能科學(xué)計(jì)算和數(shù)據(jù)分析的基礎(chǔ)包。本篇內(nèi)容為整理《利用Python進(jìn)行數(shù)據(jù)分析》，博主使用代碼為 Python3，部分內(nèi)容和書本有出入。利用 Python 進(jìn)行科學(xué)計(jì)算的實(shí)用指南。本書重點(diǎn)介紹了用于高效解決各種數(shù)據(jù)分析問...

wushuiyong 2019-07-31 11:11 評(píng)論0 收藏0