題目描述
在一個(gè)二維數(shù)組中截酷，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序狮鸭。請(qǐng)完成一個(gè)函數(shù)合搅，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)歧蕉。
方法一：
直接暴力搜索
方法二：
按行搜索，如果第i行的第1個(gè)數(shù)小于等于target康铭，且最后一個(gè)數(shù)大于等于target惯退，則搜索這一行，否則直接跳過(guò)這一行
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if( array.empty() )
return false;
for( int i=0;i<array.size();i++ )
{
int col = array[i].size();
if( col == 0 )
continue;
else if( array[i][0] <= target && array[i][col-1] >= target )
for( int j=0;j<col;j++ )
if( array[i][j] == target )
return true;
}
return false;
}
};
方法三：
從二維數(shù)組的右上角開(kāi)始搜索从藤，即第一行的最后一個(gè)數(shù)催跪，記作array[row][col]，row = 0夷野，col = array[0].size()-1懊蒸，如果相等則返回True，如果小于target則row++悯搔，如果大于target則col--
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if( array.empty() )
return false;
int row = 0;
int col = array[0].size()-1;
while( row < array.size() && col >= 0 )
{
if( array[row][col] == target )
return true;
else if( array[row][col] > target )
col--;
else if( array[row][col] < target )
row++;
}
return false;
}
};
