欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

74. Search a 2D Matrix

程序员文章站 2022-07-14 17:53:51
...

Description

https://leetcode.com/problems/search-a-2d-matrix/
在一个二维矩阵中,查找某个元素是否存在。

  • 矩阵每行从小到大排列
  • 矩阵每列从小到大排列

Solving Ideas

把矩阵看作一维的已排序的数组,使用 二分查找算法 进行搜索。

时间复杂度:O(log(mn))O(log(mn))
空间复杂度:O(1)O(1)

Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;
        
        int rows = matrix.length, cols = matrix[0].length;
        int begin = 0, end = rows * cols - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            int midVal = matrix[mid / cols][mid % cols];
            if (midVal == target) return true;
            if (midVal < target) begin = mid + 1;
            else end = mid - 1;
        }
        return false;
    }
}

《剑指offer》二维数组中的查找

时间复杂度:O(m+n)O(m+n)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) return false;

        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}