Easy understand O(log(m)+log(n)) solution


  • -3
    C

    Every time I choose the center num of matrix, and compare it with target, if mid > target, target cannot be in downright, recursively search the other three part vice versa. f(mn) = 3f(mn/4) + 1, so the time complexity should be O(log(m)+log(n)). But my runtime only beat 2.91% of java submission. Is there anything wrong with my code?

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            return searchMatrix(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
        }
        //i1, i2, j1, j2 to denote search area
        boolean searchMatrix(int[][] matrix, int target, int i1, int i2, int j1, int j2) { 
            if(i1 > i2 || j1 > j2 || i1 < 0 || j1 < 0 || i2 >= matrix.length || j2 >= matrix[0].length) return false; 
            int im = (i1 + i2)/2, jm = (j1 + j2)/2;
            int mid = matrix[im][jm];
            if(mid == target) return true;
            // if mid > target, target cannot be in downright
            // then search upleft, upright, downleft 左上,右上,左下
            else if(mid > target) return searchMatrix(matrix, target, i1, im, j1, jm-1) || searchMatrix(matrix, target, i1, im-1, jm, j2) || searchMatrix(matrix, target, im+1, i2, j1, jm-1);
            // 右上,左下,右下
            else return searchMatrix(matrix, target, i1, im, jm+1, j2) || searchMatrix(matrix, target, im+1, i2, j1, jm) || searchMatrix(matrix, target, im+1, i2, jm+1, j2);
        }
    }
    

    Blog
    Github


  • 0

    Hi,

    If you could divide the left into two parts, not three parts, then that will reduce function call. As a result, it will speed up. So the main drawback for this recursive method is the function call and stack overhead. I don't know if it can be changed to iterative method. I guess not.


  • 0
    C

    good suggestion, but I haven't think up a two parts divide solution.


  • 0

    Just merge the adjacent parts into one. Like up-left and up-right can be merged into one part. And down-left is another part.


  • 0
    C

    cool, I'll try.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.