74&240. Search a 2D Matrix I & II

Search a 2D Matrix I

You are given an m x n integer matrix matrix with the following two properties:

• Each row is sorted in non-decreasing order.

• The first integer of each row is greater than the last integer of the previous row.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

My Solutions:

因为所有数字都是递增的，可以用二分法。用数字的个数来定位数字在哪个格子。

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

        int row = matrix.length, col = matrix[0].length;
        int begin = 0, end = row * col - 1;
        
        if (target < matrix[0][0] || target > matrix[row - 1][col - 1]) return false;
        
        while (begin + 1 < end) {
            int mid = begin + (end - begin) / 2;
            int midValue = matrix[mid / col][mid % col];
            
            if (midValue == target) return true;
            else if (midValue < target) begin = mid;
            else end = mid;
        }
        if (matrix[begin / col][begin % col] == target) return true;
        if (matrix[end / col][end % col] == target) return true;
        return false;
    }
}

Search a 2D Matrix II

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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 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

My Solutions:

从matrix的右上角或者左下角找起，如果右上角的数字比target小，说明要移动行数，往下一行找。如果右上角的数字比target大，说明要移动列数，往左边一列找。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int row = 0, col = matrix[0].length - 1;
    
    while (col >= 0 && row <= matrix.length - 1) {
        
        // can use rightTop or leftBottom
        int rightTop = matrix[row][col];
        if (rightTop == target) return true;
        if (rightTop < target) row++;
        else col--;
    }
    return false;
}