[LeetCode] 74. Search a 2D Matrix 搜索一個(gè)二維矩陣

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)值所在的行的位置，然后在該行上再用一次二分查找法來(lái)找是否存在目標(biāo)值。對(duì)于第一個(gè)二分查找，由于第一列的數(shù)中可能沒(méi)有 target 值，該如何查找呢，如果是查找第一個(gè)不小于目標(biāo)值的數(shù)，當(dāng) target 在第一列時(shí)，會(huì)返回 target 所在的行，但若 target 不在的話(huà)，有可能會(huì)返回下一行，不好統(tǒng)一。所以可以查找第一個(gè)大于目標(biāo)值的數(shù)，也就是總結(jié)帖中的第三類(lèi)，這樣只要回退一個(gè)，就一定是 target 所在的行。但需要注意的一點(diǎn)是，如果返回的是0，就不能回退了，以免越界，記得要判斷一下。找到了 target 所在的行數(shù)，就可以再次使用二分搜索，此時(shí)就是總結(jié)帖中的第一類(lèi)了，查找和 target 值相同的數(shù)，也是最簡(jiǎn)單的一類(lèi)，分分鐘搞定即可，參見(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)，代碼很好寫(xiě)出來(lái)了：

解法二：

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，說(shuō)明要減小數(shù)字，則列數(shù)j自減1；若小于 target，說(shuō)明要增加數(shù)字，行數(shù)i自增1。若 while 循環(huán)退出了還是沒(méi)找到 target，直接返回 false 即可，參見(jiàn)代碼如下：

解法三：

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;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(74.搜索一個(gè)二維矩陣)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)搜索一個(gè)二維矩陣內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論