題目描述: 在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。 題目分析: 根據二維數組的特點可知,二維數組相當於一個矩陣; 根據題意可知該數組是有序的,因此 ...
題目描述:
在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。
題目分析:
- 根據二維數組的特點可知,二維數組相當於一個矩陣;
- 根據題意可知該數組是有序的,因此該矩陣元素相當於是從小到大排列的;
- 如果從左下角開始查找較方便,因為左下角的值向上是遞減的,向右是遞增的;
- 當從左下角開始比較時,如果target傳入的數大於它則列數加一進行比較 ,如果小於它則行數減一進行比較。
代碼:
1 public class Solution { 2 public boolean Find(int target, int [][] array) { 3 int rows = array.length; 4 //定義行數 5 int lies = array[0].length; 6 //定義列數 7 int i = 0; 8 //i用於計數 9 while((rows>0)&&(i<lies)) 10 //while中不滿足條件時即停止迴圈 11 { 12 if(target>array[rows-1][i]) 13 //當目標大於左下角的值時,讓列數自增 14 { 15 i++; 16 } 17 else if(target<array[rows-1][i]) 18 //當目標小於左下角的值時,讓行數自減 19 { 20 rows--; 21 }else 22 { 23 //當前兩種都不是時,說明找到目標 24 return true; 25 } 26 } 27 //遍歷完還沒找到,說明目標在數組中不存在 28 return false; 29 } 30 }