前言說明
算法學習，日常刷題記錄。
題目連接
題目內(nèi)容
在一個n * m的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個高效的函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
示例:
現(xiàn)有矩陣matrix如下：
給定target = 5，返回true。
給定target = 20，返回false。
限制:
0 <= n <= 1000
0 <= m <= 1000
分析過程
方法1
直接用暴力算法，兩層遍歷查找，代碼如下：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 暴力算法，直接兩層遍歷查找
for (int[] nums : matrix) {
for (int num : nums) {
if (target == num) {
// 若找到target，返回true
return true;
}
}
}
// 若兩層遍歷完也找不到target，返回false
return false;
}
}
提交代碼，運行結(jié)果如下：
執(zhí)行用時0ms，時間擊敗100.00%的用戶，內(nèi)存消耗4MB，空間擊敗78.44%的用戶。
方法2
方法1為暴力破解，肯定是不可取的，沒有使用到題目的條件：每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。
所以方法2采用線性查找法，利用二維數(shù)組matrix行遞增和列遞增的特點，不斷縮小范圍查找。
設(shè)置行標row初始為0，列標col初始為列長度減1，查找時若等于目標值target，返回true，結(jié)束。
若小于目標值target，行標row加1，直到找到目標值target為止，否則直到行標row等于行長度減1結(jié)束。
若大于目標值target，列標col減1，直到找到目標值target為止，否則直到行標row等于0結(jié)束。
若結(jié)束后還沒有找到目標值target，返回false，結(jié)束。
例如：上面的例子查找5，行標row初始為0，列標col初始為4。
matrix[0][4] = 15，15 > 5，大于目標值target，列標col減1等于3。
matrix[0][3] = 11，11 > 5，大于目標值target，列標col減1等于2。
matrix[0][2] = 7，7 > 5，大于目標值target，列標col減1等于1。
matrix[0][1] = 4，4 < 5，小于目標值target，行標row加1等于1。
matrix[1][1] = 5，5 = 5，等于目標值target，找到目標值，返回true，結(jié)束。
代碼如下：
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
// 線性查找法，利用行遞增和列遞增的特點，不斷縮小范圍
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
// 先把二維數(shù)組為空的情況排除掉
return false;
}
// 定義行標，初始值為0
int row = 0;
// 定義列標，初始值為二維數(shù)組matrix的列長度減1
int col = matrix[0].length - 1;
// 循環(huán)，行標擴大直到二維數(shù)組matrix的行長度減1，列標縮小直到0
while (row < matrix.length && col >= 0) {
// 獲取當前行標和列標下的二維數(shù)組matrix的元素
int num = matrix[row][col];
if (target == num) {
// 若目標值target等于當前元素，那么二維數(shù)組matrix中含有目標值target，返回true
return true;
} else if (target > num) {
// 若目標值target大于當前元素，行標加1
++row;
} else {
// 若目標值target小于當前元素，列標減1
--col;
}
}
// 若能循環(huán)結(jié)束，那么在二維數(shù)組matrix中沒有找到目標值target，返回false
return false;
}
}
提交代碼，運行結(jié)果如下：
執(zhí)行用時0ms，時間擊敗100.00%的用戶，內(nèi)存消耗44.2MB，空間擊敗32.00%的用戶。
總結(jié)解題
運行結(jié)果分析
運行時間：方法2的線性查找法不比方法1的暴力破解法快多少，都是擊敗100%。
運行空間：方法2的線性查找法比方法1的暴力破解法還要多一點。
原因：方法2的線性查找法的運行空間的確是會比方法1的暴力破解法多一點，但是運行時間相差不大可能是題目執(zhí)行的用例不夠大造成的。
方法1復雜度
時間復雜度：O(nm)，n為二維數(shù)組中的行長度，m為二維數(shù)組中的列長度。
因為是兩層for循環(huán)嵌套遍歷，第一層遍歷是n次，第二層遍歷是m次，所以用乘法，一共等于n * m次。
空間復雜度：O(1)。
方法2復雜度
時間復雜度：O(n + m)，n為二維數(shù)組中的行長度，m為二維數(shù)組中的列長度。
因為行標row最多加n次，列標col最多減m次，所以用加法，一共等于n + m次。
空間復雜度：O(1)。
原文鏈接
原文鏈接：二維數(shù)組中的查找
