這篇文章主要介紹“C++怎么實(shí)現(xiàn)搜索一個(gè)二維矩陣”，在日常操作中，相信很多人在C++怎么實(shí)現(xiàn)搜索一個(gè)二維矩陣問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++怎么實(shí)現(xiàn)搜索一個(gè)二維矩陣”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！
為萬柏林等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及萬柏林網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站建設(shè)、網(wǎng)站制作、萬柏林網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！
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>& 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>& 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>& 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;
}
}; 到此，關(guān)于“C++怎么實(shí)現(xiàn)搜索一個(gè)二維矩陣”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
