題目
在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序朴沿，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)办龄，判斷數(shù)組中是否含有該整數(shù)。
考察點和難度
- 考察知識點：數(shù)組
- 難度：4星（共5星）
分析
最簡單的求解方式是遍歷整個二維數(shù)組溯乒，可以查詢到是否有目標(biāo)值，但是時間復(fù)雜度為O(rows * cols)澡绩，面試官是不會滿意的。
為了降低時間復(fù)雜度俺附，需要運用該二維數(shù)組的特性肥卡，即橫向和縱向的遞增特性。
該二維數(shù)組中的任意一個點P事镣，其左前區(qū)域都小于點P的值步鉴，其右后區(qū)域都大于點P的值，因此可以利用該特性在查詢時縮小查詢范圍璃哟。
從最右上角的點P出發(fā)氛琢，如果點P的值等于目標(biāo)值，則直接輸出true沮稚；如果點P的值大于目標(biāo)值艺沼，可以往左查找第一個小于等于目標(biāo)值的點PL，此時點PL成為新的“右上角”蕴掏，且點PL的右后部分區(qū)域的數(shù)值由于肯定大于目標(biāo)值障般，因此可以被剔除出查詢范圍；如果點P的值小于目標(biāo)值盛杰，可以往下查詢第一個大于等于目標(biāo)值的點PD挽荡，此時點PD成為新的“右上角”，且點PD的左前部分區(qū)域的數(shù)值由于肯定小于目標(biāo)值即供，因此也可以被剔除出查詢范圍定拟。得到新的“右上角”之后，重復(fù)該操作逗嫡，就能遍歷整個二維數(shù)組來查詢目標(biāo)值青自，且由于只在橫向和縱向往左下角移動，剔除了無需查詢的區(qū)域范圍驱证，因此時間復(fù)雜度為O(rows + cols)延窜。
為什么從右上角出發(fā)開始查詢？對于右上角的點P來說抹锄，其左邊的數(shù)值都小于點P的值逆瑞，其下面的數(shù)值都大于點P的數(shù)值，當(dāng)給定目標(biāo)值之后伙单，如果目標(biāo)值小于點P的數(shù)值获高，那么點P所在列就可以被剔除；如果目標(biāo)值大于點P的數(shù)值吻育，那么點P所在行就可以被剔除念秧，這樣就縮小了查詢范圍。
從左下角出發(fā)扫沼，往右上角查詢也是可以的出爹。
代碼實現(xiàn)（java）
public boolean hasNumInArray(int[][] array, int rows, int cols, int num) {
// 檢查輸入?yún)?shù)
if (array == null) {
throw new NullPointerException();
}
if (rows < 1 || cols < 1) {
throw new IllegalArgumentException();
}
int rowSize = array.length;
if (rowSize != rows) {
throw new IllegalArgumentException();
}
int colSize = array[0].length;
if (colSize != cols) {
throw new IllegalArgumentException();
}
// 從右上角數(shù)字開始庄吼，往左下角找目標(biāo)數(shù)字，理論上時間復(fù)雜度為O(rows+cols)
int i = 0, j = cols - 1;
while ((i <= (rows - 1)) && (j >= 0)) {
// 判斷當(dāng)前右上角的值是否為目標(biāo)值
if (array[i][j] == num) {
return true;
} else if (array[i][j] > num) {
// 當(dāng)前右上角的值比目標(biāo)值大严就，則往左找新的“右上角”总寻，且新的“右上角”的右后部分區(qū)域由于肯定大于目標(biāo)值，因此可被剔除
while ((j >= 0) && (array[i][j] > num)) {
j = j - 1;
}
} else {
// 當(dāng)前右上角的值比目標(biāo)值小梢为，則往下找新的“右上角”渐行，且新的“右上角”的左前部分區(qū)域由于肯定小于目標(biāo)值，因此可被剔除
while ((i <= (rows - 1) && (array[i][j]) < num)) {
i = i + 1;
}
}
}
return false;
}
