240.Search-a-2D-Matrix-II.md

240. Search a 2D Matrix II

---

题目地址

https://leetcode.com/problems/search-a-2d-matrix-ii/

题目描述

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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:
Consider the following 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]
]
Given target = 5, return true.

Given target = 20, return false.

代码

Approach #1 Binary Search

Time complexity :O(log(n!))

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0)		return false;
    
    int shoterDim = Math.min(matrix.length, matrix[0].length);
    for (int start = 0; start < shorterDim; start++) {
      boolean verticalFound = binarySearch(matrix, target, start, true);
      boolean horizontalFound = binarySearch(matrix, target, start, false);
      
      if (verticalFound || horizontalFound) {
        return true;
      }
    }
    
    return false;
  }
  
  private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
    int left = start;
    int right = vertical ? matrix[0].length - 1: matrix.length - 1;
    
    while (left <= right) {
      int mid = (left + right) / 2;
      if (vertical) {
        if (matrix[left][mid] < target) {
          left = mid + 1;
        } else if (matrix[left][mid] > target) {
          right = mid - 1;
        } else {
          return true;
        }
      } else {
        if (matrix[mid][left] < target) {
          left = mid + 1;
        } else if (matrix[mid][left] > target) {
          right = mid - 1;
        } else {
          return true;
        }
      }
    }
    
    return false;
  }
}

Approach #2 Divide and Conquer

class Solution {
  private int[][] matrix;
  private int target;
  
  public boolean searchMatrix(int[][] mat, int target) {
    if (matrix == null || matrix.length == 0)		return false;
    
    matrix = mat;
    this.target = target;
    
    return searchRec(0, 0, matrix[0].length - 1, matrix.length - 1);
  }
  
  private boolean searchRec(int left, int up, int right, int down) {
    if (left > right || up > down) {
      return false;
    } else if (target < matrix[up][left] || target > matrix[down][right]) {
      return false;
    }
    
    int mid = left + (right - left) / 2;
    // Locate `row` such that matrix[row-1][mid] < target < matrix[row][mid]
    int row = up;
    while (row <= down && matrix[row][mid] <= target) {
      if (matrix[row][mid] == target) 	return true;
      row++;
    }
    
    return searchRec(left, row, mid - 1, down)
      || searchRec(mid + 1, up, right, row - 1);
  }
}

Approach #3

Time complexity : O(n+m)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.length - 1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { // found it
                return true;
            }
        }

        return false;
    }
}