[Leetcode]74. Search a 2D Matrix(C++)

题目描述

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.

例子

例子 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true

例子 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

-10^4 <= matrix[i][j], target <= 10^4

解题思路

由于矩阵每一行都是有序的，且每一行都比上一行大，因此思路很明确，可以使用两次二分查找，第一次找到有可能包含目标元素的行（首元素比目标值小，且下一行首元素比目标值大），第二次在该行查找该元素即可，代码如下：

#include <vector>

class Solution {
public:
    bool searchMatrix(std::vector<std::vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int left = 0;
        int right = m - 1;
        while (left < right) {
            int mid = (left + right) / 2 + 1;
            if (matrix[mid][0] > target) {
                right = mid - 1;
            } else if (matrix[mid][0] < target) {
                left = mid;
            } else {
                return true;
            }
        }

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

        return matrix[row][left] == target;
    }
};

时间复杂度: O(log max(m,n))
空间复杂度: O(1)

GitHub 代码同步地址： 74.SearchA2DMatrix.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions