劍指offer第二季第二題
這里我們將矩陣旋轉成二叉樹 如下圖所示
從右上角的元素出發
1.如果num>target 那么我們需要向左查找 也就是列坐標減一
2如果num<target 那么我們需要向右查找 也就是行坐標加一
具體代碼如下
public class 二維陣列找目標值的問題 {
/*刷玩letcode之后的感想 可以直接把矩陣旋轉 結構變成類似于平衡二叉樹 這樣我們通過二叉樹的搜索方法 結合題目 大概可以得出
* 如下圖所示
* 當target比當前節點的值小時 列索引的值減一 這樣相當于我們旋轉后的樹向左移動
* 當target比當前節點的值大時 行索引的值加一 這樣相當于我們旋轉后的樹向右移動*/
public static void main(String[] args) {
int[][] matrix = new int[][]{{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}};
boolean select = select(matrix, 18);
System.out.println(select);
}
public static boolean select(int[][] matrix,int target){
/*return null;*/
int rows =matrix.length;
int cols =matrix[0].length;
int row =0;
int col =cols-1;
int num =matrix[row][col];
while (row<=rows && col>=0){
if (target==num){
return true;
}else if(target>num){
row++;
num=matrix[row][col];
}else if (target<num){
col--;
num=matrix[row][col];
}
}
return false;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/387133.html
標籤：其他