LeetCode_每日一题3

[74] 搜索二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix/description/

• algorithms
• Medium (41.11%)
• Likes: 372
• Dislikes: -
• Total Accepted: 104.3K
• Total Submissions: 243.2K
• Testcase Example: ‘[[1,3,5,7],[10,11,16,20],[23,30,34,60]]\n3’

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

 

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

方法1: 两次二分查找

思路: 看到有序, 直接二分整起来, 两次二分, 第一次查找是否存在满足条件的行, 第二次查找是否存在 target

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

            return false;
    }
};

复杂度分析:

• 时间复杂度: O(logm + logn = logmn), m是行数, n是列数
• 空间复杂度: O(1)

方法2: 一次二分

思路: 将矩阵看作是一个有序数组, 一次二分即可

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.empty()) return false;
            int m = matrix.size(), n = matrix[0].size();
            int left = 0, right = m * n - 1, mid;

            while(left <= right){
                mid = right + left >> 1;
                int x = matrix[mid / n][mid % n];
                if(x == target){
                    return true;
                }else if(x < target){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return false;
    }
};

复杂度分析:

• 时间复杂度: O(logmn)
• 空间复杂度: O(1)