資訊專欄INFORMATION COLUMN
摘要：題目在一個二維數(shù)組中每個一維數(shù)組的長度相同，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
題目
在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
基本思路二維數(shù)組是有序的，比如下面的數(shù)據(jù)：
1 2 3 4 5 6 7 8 9
可以直接利用左下角數(shù)字開始查找：
大于：比較上移
小于：比較右移
代碼思路將二維數(shù)組看作平面坐標(biāo)系
從左下角（0,arr.length-1）開始比較：
目標(biāo)值大于坐標(biāo)值---x坐標(biāo)+1
目標(biāo)值小于坐標(biāo)值---y坐標(biāo)-1
注意：
二維數(shù)組arri中
j代表x坐標(biāo)
i代表y坐標(biāo)
代碼 function Find(target, array) {
let i = array.length - 1; // y坐標(biāo)
let j = 0; // x坐標(biāo)
return compare(target, array, i, j);
}
function compare(target, array, i, j) {
if (array[i] === undefined || array[i][j] === undefined) {
return false;
}
const temp = array[i][j];
if (target === temp) {
return true;
}
else if (target > temp) {
return compare(target, array, i, j+1);
}
else if (target < temp) {
return compare(target, array, i-1, j);
}
}
拓展：二分查找
二分查找的條件是必須有序。
和線性表的中點值進行比較，如果小就繼續(xù)在小的序列中查找，如此遞歸直到找到相同的值。
function binarySearch(data, arr, start, end) {
if (start > end) {
return -1;
}
var mid = Math.floor((end + start) / 2);
if (data == arr[mid]) {
return mid;
} else if (data < arr[mid]) {
return binarySearch(data, arr, start, mid - 1);
} else {
return binarySearch(data, arr, mid + 1, end);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100763.html
摘要：二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。 1.二維數(shù)組中的查找 在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)...
摘要：二維數(shù)組中的查找在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計算的時間復(fù)雜度是以的指數(shù)的方式遞增的，如果面試中千萬不要用遞歸法，一定要用迭代法。 二維數(shù)組中的查找 在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和...
摘要：面試題從尾到頭打印鏈表輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值面試題重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。隊列中的元素為類型。其中負數(shù)用補碼表示。 面試題2 單例(之前有整理，略) 面試題3 二維數(shù)組中的查找 public boolean find(int target, int [][] arra...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復(fù)雜度為 ...
閱讀 530·2023-04-26 00:33
閱讀 3552·2021-11-24 09:39
閱讀 2960·2021-09-22 15:34
閱讀 2332·2019-08-23 18:07
閱讀 2926·2019-08-23 18:04
閱讀 3713·2019-08-23 16:06
閱讀 2904·2019-08-23 15:27
閱讀 1626·2019-08-23 14:32
