聖地亞歌

Leetcode P0074"Search a 2D Matrix" 题解

2020/08/29 Leetcode

博文中会简要介绍Leetcode P0074题目分析及解题思路。

“Search a 2D Matrix”是一道比较有意思的题目，考察的重点在于灵活运用二分查找算法。

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, 50]
]
target = 3
Output: true
Plaintext

分成两部分来二分查找，对第一列二分查找，然后对指定行二分查找。

以下是Java的题解代码实现。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return false;
        
        int up = 0, down = matrix.length-1, midRow = 0;
        while (up <= down) {
            midRow = (up+down)/2;
            
            if (matrix[midRow][0] > target)
                down = midRow-1;
            else if (matrix[midRow][0] < target)
                up = midRow+1;
            else 
                return true;
        }
        
        if (matrix[midRow][0] > target)
            midRow -= 1;
        
        if (midRow < 0)
            return false;
        
        int left = 0, right = matrix[0].length-1, midCol = 0;
        while (left <= right) {
            midCol = (left+right)/2;
            
            if (matrix[midRow][midCol] > target) 
                right = midCol-1;
            else if (matrix[midRow][midCol] < target)
                left = midCol+1;
            else 
                return true;
        }
        
        return false;
    }
}
Java

以下是C++的题解代码实现。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return false;
        
        int up = 0, down = matrix.size()-1, midRow = 0;
        while (up <= down) {
            midRow = (up+down)/2;
            
            if (matrix[midRow][0] > target)
                down = midRow-1;
            else if (matrix[midRow][0] < target)
                up = midRow+1;
            else 
                return true;
        }
        
        if (matrix[midRow][0] > target)
            midRow -= 1;
        
        if (midRow < 0)
            return false;
        
        int left = 0, right = matrix[0].size()-1, midCol = 0;
        while (left <= right) {
            midCol = (left+right)/2;
            
            if (matrix[midRow][midCol] > target) 
                right = midCol-1;
            else if (matrix[midRow][midCol] < target)
                left = midCol+1;
            else 
                return true;
        }
        
        return false;
    }
};
C++

Search