題目描述 在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。 鏈接:https://www.nowcoder.com/questionTerminal/abc ...
題目描述
在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。 鏈接:https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?f=discussion來源:牛客網
兩種思路
一種是:
把每一行看成有序遞增的數組,
利用二分查找,
通過遍歷每一行得到答案,
時間複雜度是nlogn
public
class
Solution {
public
boolean
Find(
int
[][] array,
int
target) {
for
(
int
i=
0
;i<array.length;i++){
int
low=
0
;
int
high=array[i].length-
1
;
while
(low<=high){
int
mid=(low+high)/
2
;
if
(target>array[i][mid])
low=mid+
1
;
else
if
(target<array[i][mid])
high=mid-
1
;
else
return
true
;
}
}
return
false
;
}
}
另外一種思路是:
利用二維數組由上到下,由左到右遞增的規律,
那麼選取右上角或者左下角的元素a[row][col]與target進行比較,
當target小於元素a[row][col]時,那麼target必定在元素a所在行的左邊,
即col--;
當target大於元素a[row][col]時,那麼target必定在元素a所在列的下邊,
即row++;
public
class
Solution {
public
boolean
Find(
int
[][] array,
int
target) {
int
row=
0
;
int
col=array[
0
].length-
1
;
while
(row<=array.length-
1
&&col>=
0
){
if
(target==array[row][col])
return
true
;
else
if
(target>array[row][col])
row++;
else
col--;
}
return
false
;
}
}