您好,登錄后才能下訂單哦!
LeetCode中如何查找二維數(shù)組查找,針對這個問題,這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答,希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
二維數(shù)組中的查找
在一個 n * m 的二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個高效的函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。
示例:
現(xiàn)有矩陣 matrix 如下:
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
給定 target = 5,返回 true。
給定 target = 20,返回 false。
限制:
0 <= n <= 1000 0 <= m <= 1000
解法一
題目理解起來很簡單,一個二維數(shù)組,一個數(shù)字。判斷數(shù)組里面有沒有這個數(shù)字。
另外還有一個提干是每一行每一列都是數(shù)字遞增,待會再看看這個題干怎么利用起來。
如果只是一個數(shù)組里面找數(shù)字,那么很容易想到的就是直接遍歷。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return false; } int rows = matrix.length, columns = matrix[0].length; for (int i = 0; i < rows; i++) { for (int j = 0; j < columns; j++) { if (matrix[i][j] == target) { return true; } } } return false; } }
方法消耗情況
執(zhí)行用時(shí):0-1 ms 內(nèi)存消耗:44.3 MB
時(shí)間復(fù)雜度
由于用到了二維數(shù)組的遍歷,所以時(shí)間復(fù)雜度就是O(mn),用到了時(shí)間復(fù)雜度的乘法計(jì)算。
空間復(fù)雜度
除了本身的數(shù)組,只用到了幾個變量,所以空間復(fù)雜度是O(1)。
解法二
接下來我們就看看怎么利用剛才說到的數(shù)字遞增題干,得出新的更簡便的解法呢?
由于每一行的數(shù)字都是按循序排列的,所以我們很容易就想到用二分法來解決,也就是遍歷每一行,然后在每一行里面進(jìn)行二分法查詢。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { for (int i = 0; i < matrix.length; i++) { int left = 0; int right = matrix[0].length-1; while (left<=right) { int middle = (left + right) / 2; if (target == matrix[i][middle]) { return true; } if (target > matrix[i][middle]) { left = middle + 1; } else { right = middle - 1; } } } return false; } }
方法消耗情況
執(zhí)行用時(shí):0-1 ms 內(nèi)存消耗:44.4 MB
時(shí)間復(fù)雜度
二分法的復(fù)雜度大家應(yīng)該都知道吧,O(logn)。具體算法就是 N *(1/2)^x=1,得出來x=logn,底數(shù)為2。
所以在外面套一個循環(huán),總的時(shí)間復(fù)雜度就為O(mlogn),底數(shù)為2
空間復(fù)雜度
由于也沒有用到額外的跟n有關(guān)的空間,所以空間復(fù)雜度是O(1)。
解法三
但是,剛才的解法還是沒有完全用到題目的特性,這個二維數(shù)組不僅是每行進(jìn)行了排序,每列也進(jìn)行了排序。
所以,該怎么解呢?
我們可以把這個數(shù)組轉(zhuǎn)個角度看看,轉(zhuǎn)45度角:
[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]
15 11 19 7 12 22 4 8 16 24 1 5 9 17 30 ...
下面就不寫了,是不是像一個二叉樹的結(jié)構(gòu)了?而且每個節(jié)點(diǎn)的左分支是一定小于這個元素的,右分支是一定大于這個元素的。
那么根據(jù)這個特點(diǎn),我們又可以寫出一種更簡便的算法了,也就是從第一行的最后一個數(shù)字開始,依次和目標(biāo)值比較,如果目標(biāo)值大于這個節(jié)點(diǎn)數(shù),就把節(jié)點(diǎn)往下移動,也就是行數(shù)+1。如果目標(biāo)值小于這個節(jié)點(diǎn)數(shù),就把節(jié)點(diǎn)向左移動,也就是列數(shù)-1。
class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int i = matrix.length - 1, j = 0; while(i >= 0 && j < matrix[0].length) { if(matrix[i][j] > target) i--; else if(matrix[i][j] < target) j++; else return true; } return false; } }
方法消耗情況
執(zhí)行用時(shí):0-1 ms 內(nèi)存消耗:44.5 MB
時(shí)間復(fù)雜度
代碼量確實(shí)少了很多,那么時(shí)間復(fù)雜度有沒有減少呢?
可以看到,只有一個while循環(huán),從右上角開始找,如果最壞情況就是找到左下角,也就是移動到最下面一行的第一列,那么時(shí)間復(fù)雜度就是O(m+n)了。
一個是mlogn(底數(shù)為2),一個是m+n,也不能斷定哪個小,但是m和n比較大的時(shí)候肯定是加法得出的結(jié)果比較小的,所以這種解法應(yīng)該是最優(yōu)解法了。
關(guān)于LeetCode中如何查找二維數(shù)組查找問題的解答就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,如果你還有很多疑惑沒有解開,可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。