leetcode刷題20——搜尋矩陣系列

1.搜尋二維矩陣

編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目标值。該矩陣具有如下特性：

每行中的整數從左到右按升序排列；每行的第一個整數大于前一行的最後一個整數。

考察知識點：二分查找

思路：若将矩陣每一行拼接在上一行的末尾，則會得到一個升序數組，我們可以在該數組上二分找到目标元素。代碼實作時，可以二分升序數組的下标，将其映射到原矩陣的行和列上。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int left=0,right=m*n-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(matrix[mid/n][mid%n]==target)
                return true;
            else if(matrix[mid/n][mid%n]<target)
                left=mid+1;
            else
                right=mid-1;
        }
        return false;
    }
};
           

2.搜尋二維矩陣 II

編寫一個高效的算法來搜尋 m x n 矩陣 matrix 中的一個目标值 target 。該矩陣具有以下特性：

每行的元素從左到右升序排列；每列的元素從上到下升序排列。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int i = 0,j = n-1;
        while(i < m && j >= 0) 
        {
            if(matrix[i][j] == target) 
                return true;
            if(matrix[i][j] < target) 
                ++ i;
            else 
                -- j;
        }
        return false;
    }
};