您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++如何實(shí)現(xiàn)搜索二維矩陣功能”的有關(guān)知識(shí),在實(shí)際案例的操作過程中,不少人都會(huì)遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
這道題要求搜索一個(gè)二維矩陣,由于給的矩陣是有序的,所以很自然的想到要用二分查找法,可以在第一列上先用一次二分查找法找到目標(biāo)值所在的行的位置,然后在該行上再用一次二分查找法來找是否存在目標(biāo)值。對(duì)于第一個(gè)二分查找,由于第一列的數(shù)中可能沒有 target 值,該如何查找呢,如果是查找第一個(gè)不小于目標(biāo)值的數(shù),當(dāng) target 在第一列時(shí),會(huì)返回 target 所在的行,但若 target 不在的話,有可能會(huì)返回下一行,不好統(tǒng)一。所以可以查找第一個(gè)大于目標(biāo)值的數(shù),也就是總結(jié)帖中的第三類,這樣只要回退一個(gè),就一定是 target 所在的行。但需要注意的一點(diǎn)是,如果返回的是0,就不能回退了,以免越界,記得要判斷一下。找到了 target 所在的行數(shù),就可以再次使用二分搜索,此時(shí)就是總結(jié)帖中的第一類了,查找和 target 值相同的數(shù),也是最簡(jiǎn)單的一類,分分鐘搞定即可,參見代碼如下:
解法一:
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int left = 0, right = matrix.size(); while (left < right) { int mid = (left + right) / 2; if (matrix[mid][0] == target) return true; if (matrix[mid][0] < target) left = mid + 1; else right = mid; } int tmp = (right > 0) ? (right - 1) : right; left = 0; right = matrix[tmp].size(); while (left < right) { int mid = (left + right) / 2; if (matrix[tmp][mid] == target) return true; if (matrix[tmp][mid] < target) left = mid + 1; else right = mid; } return false; } };
當(dāng)然這道題也可以使用一次二分查找法,如果我們按S型遍歷該二維數(shù)組,可以得到一個(gè)有序的一維數(shù)組,只需要用一次二分查找法,而關(guān)鍵就在于坐標(biāo)的轉(zhuǎn)換,如何把二維坐標(biāo)和一維坐標(biāo)轉(zhuǎn)換是關(guān)鍵點(diǎn),把一個(gè)長(zhǎng)度為n的一維數(shù)組轉(zhuǎn)化為 m*n 的二維數(shù)組 (m*n = n)后,那么原一維數(shù)組中下標(biāo)為i的元素將出現(xiàn)在二維數(shù)組中的 [i/n][i%n] 的位置,有了這一點(diǎn),代碼很好寫出來了:
解法二:
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int m = matrix.size(), n = matrix[0].size(); int left = 0, right = m * n; while (left < right) { int mid = (left + right) / 2; if (matrix[mid / n][mid % n] == target) return true; if (matrix[mid / n][mid % n] < target) left = mid + 1; else right = mid; } return false; } };
這道題其實(shí)也可以不用二分搜索法,直接使用雙指針也是可以的,i指向0,j指向列數(shù),這樣第一個(gè)被驗(yàn)證的數(shù)就是二維數(shù)組右上角的數(shù)字,假如這個(gè)數(shù)字等于 target,直接返回 true;若大于 target,說明要減小數(shù)字,則列數(shù)j自減1;若小于 target,說明要增加數(shù)字,行數(shù)i自增1。若 while 循環(huán)退出了還是沒找到 target,直接返回 false 即可,參見代碼如下:
解法三:
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty() || matrix[0].empty()) return false; int i = 0, j = (int)matrix[0].size() - 1; while (i < matrix.size() && j >= 0) { if (matrix[i][j] == target) return true; else if (matrix[i][j] > target) --j; else ++i; } return false; } };
“C++如何實(shí)現(xiàn)搜索二維矩陣功能”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。