現(xiàn)在有一個(gè)行和列都排好序的矩陣,請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法腺办,快速查找矩陣中是否含有值x。
給定一個(gè)int矩陣mat糟描,同時(shí)給定矩陣大小nxm及待查找的數(shù)x怀喉,請(qǐng)返回一個(gè)bool值,代表矩陣中是否存在x蚓挤。所有矩陣中數(shù)字及x均為int范圍內(nèi)整數(shù)磺送。保證n和m均小于等于1000驻子。
測(cè)試樣例:
輸入:[[1,2,3],[4,5,6],[7,8,9]],3,3,10
返回:false
// find X in a sorted (column and row) matrix
class Finder {
public:
bool findX(vector<vector<int> > mat, int n, int m, int x) {
// write code here
// int curr_val = mat[0][m-1];
int i = 0, j = m - 1;
while(i < n && j >= 0){
if(x > mat[i][j]){
++i;
}else if(x < mat[i][j]){
--j;
}
else{
return true;
}
}
return false;
}
};