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

题目描述

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

Integers in each row are sorted in ascending from left to right.

Integers in each column are sorted in ascending from top to bottom.

例子

例子 1

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

例子 2

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false

Follow Up

Note

Constraints

m == matrix.length

n == matrix[i].length

1 <= n, m <= 300

-10^9 <= matix[i][j] <= 10^9

All the integers in each row are sorted in ascending order.

All the integers in each column are sorted in ascending order.

-10^9 <= target <= 10^9

解题思路

[Leetcode]74. Search a 2D Matrix(C++) 的变种版本，这次给定矩阵符合条件是，每一行同样是已排序，但每一行不一定所有元素都比上一行大，只满足每一列是升序。也就是我们在上一题中用过的二分查找锁定某一行的方法不可行了，因为可能有多行满足第一个元素比target 小，最后一个元素比 target 大的条件。因此我们需要对每一行进行一次二分查找，不过可以利用每一列也是升序的特点，对每行行首和行尾分别进行一次二分查找，筛掉所有元素都大于/小于 target 的行，对剩余行进行二查找即可。代码如下：

#include <vector>

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

        std::pair<int, int> valid_range{0, m - 1};

        int left = 0;
        int right = m - 1;
        // filter out rows where all elements are larger than target
        while (left < right) {
            int mid = (left + right) / 2 + 1;
            if (matrix[mid][0] > target) {
                right = mid - 1;
                valid_range.second = right;
            } else if (matrix[mid][0] < target) {
                left = mid;
            } else {
                return true;
            }
        }

        // filter out rows where all elements are smaller than target
        left = 0;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[mid][n - 1] < target) {
                left = mid + 1;
                valid_range.first = left;
            } else if (matrix[mid][n - 1] > target) {
                right = mid;
            } else {
                return true;
            }
        }

        // for the rest rows, do a binary search for each row
        for (int r = valid_range.first; r <= valid_range.second; ++r) {
            left = 0;
            right = n - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (matrix[r][mid] < target) {
                    left = mid + 1;
                } else if (matrix[r][mid] > target) {
                    right = mid - 1;
                } else {
                    return true;
                }
            }
        }

        return false;
    }
};

时间复杂度: O(mlog n) – 由于有剪枝，实际复杂度会更小一点
空间复杂度: O(1)

GitHub 代码同步地址： 240.SearchA2DMatrixIi.cpp

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