題目描述
在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
分析：
? ? ? ?觀察下面的數(shù)組，要先找規(guī)律，首先數(shù)組是按序排列的，同一行右邊比左邊小，同一列下面比上面大。因此比較時從右上角比較能夠減少比較的次數(shù)：比較的邏輯是：
? ? ? ?首先從數(shù)組的右上角開始，如果給定的值target大于右上角的值那么證明不在第一行，此時行數(shù)+1，列數(shù)不變。這時要比較的是第二行的最后一個數(shù)值如果這個數(shù)target比9大則換行，如果比9小就減小列數(shù)直到遇到比這個數(shù)target小的值時換行，如果是相等的話返回真，如果超出界限的話直接返回假，以此類推找出這個數(shù)，或者返回false說明這個數(shù)不在數(shù)組中。
源碼：
public class Solution {
? ? public boolean Find(int target, int [][] array)
? ? {
? ? ? ? int row=array.length;
? ? ? ? int i=0;
? ? ? ? int col=array[0].length;
? ? ? ? int j=array[i].length-1;
? ? ? ? while(i<row&&j>=0)
? ? ? ? {
? ? ? ? ? ? if(target==array[i][j])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? ? ? if(target>array[i][j])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }
}
