LeetCode240——搜索二维矩阵II

我的LeetCode代码仓：https://github.com/617076674/LeetCode

原题链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/description/

题目描述：

知识点：分治算法、二分查找法

思路一：暴力**法

时间复杂度是O(m * n)，其中m为矩形的行数，n为矩阵的列数。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (0 == m) {
            return false;
        }
        int n = matrix[0].length;
        if (0 == n) {
            return false;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (target == matrix[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

LeetCode解题报告：

思路二：分治算法

思路一没有利用题目的条件——“每行的元素从左到右升序排列，每列的元素从上到下升序排列”。为了利用这一条件，我们从矩阵右上角开始遍历。

（1）如果目标值等于当前值，直接返回true。

（2）如果目标值小于当前值，说明当前列的元素均不满足，我们遍历下一列（即左侧一列）。

（3）如果目标值大于当前值，说明当前行的元素均不满足，我们遍历下一行。

时间复杂度是O(m + n)，其中m为矩形的行数，n为矩阵的列数。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (0 == m) {
            return false;
        }
        int n = matrix[0].length;
        if (0 == n) {
            return false;
        }
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (target < matrix[row][col]) {
                col--;
            } else if (target > matrix[row][col]) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }
}

LeetCode解题报告：

思路三：二分查找法

首先对第一列元素进行二分查找，查找值大于等于target的元素所在列，如果找到了target值，直接返回true。否则，对第一个元素小于target的行，每一行都进行二分查找寻找target的值。

时间复杂度在最差情况下是O(m * logn)，其中m为矩形的行数，n为矩阵的列数。空间复杂度是O(1)。

JAVA代码：

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (0 == m) {
            return false;
        }
        int n = matrix[0].length;
        if (0 == n) {
            return false;
        }
        int left = 0, right = m - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (matrix[mid][0] > target) {
                right = mid - 1;
            } else if (matrix[mid][0] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        for (int i = 0; i <= right; i++) {
            int temp = Arrays.binarySearch(matrix[i], target);
            if (temp >=0 && temp < n) {
                return true;
            }
        }
        return false;
    }
}

LeetCode解题报告：