本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫
文章目錄
4. 二維數組中的查找題目連結題目描述解題思路
4. 二維數組中的查找
題目連結
牛客網
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github
題目描述
給定一個二維數組，其每一行從左到右遞增排序，從上到下也是遞增排序。給定一個數，判斷這個數是否在該二維數組中。
Consider the following 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]
]
Given target = 5, return true.
Given target = 20, return false.
Copy to clipboardErrorCopied
解題思路
要求時間複雜度 O(M + N)，空間複雜度 O(1)。其中 M 為行數，N 為 列數。
該二維數組中的一個數，小於它的數一定在其左邊，大於它的數一定在其下邊。因此，從右上角開始查找，就可以根據target和當前元素的大小關係來縮小查找區間，當前元素的查找區間為左下角的所有元素。
package 二維數組中的查找;/*
作者 :XiangLin
文件 :FindTarget.java
IDE :IntelliJ IDEA
*/
public class FindTarget {
public boolean Find(int tareget,int[][] martix){
if(martix == null || martix.length == 0 || martix[0].length == 0) //判斷二維數組是否存在
return false;
int rows = martix.length,cols = martix[0].length; //求出二維數組列和行的長度
int r = 0,c = cols - 1; //初始狀態定位到二維數組的右上角
while (r < rows - 1 && c >= 0){
if (tareget == martix[r][c]) //找到目標值的情況
return true;
else if(tareget > martix[r][c]) //目標值比當前大，說明行要增加,往下走
r ++;
else //目標值比當前小，說明列要減小,往左走
c --;
}
return false;
}
public static void main(String[] args) {
FindTarget find = new FindTarget();
int[][] martix = {
{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}
};
int target = 0;
boolean x = find.Find(target,martix);
System.out.println(x);
}
}
輸出：
false