slow solution~ split into 4 matrix~


  • 0
    Y
        private int[][] m = null;
        private int w = 0;
        private int h = 0;
    
        public boolean searchMatrix(int[][] matrix, int target) {
            if (null == matrix || 0 == matrix.length)   return false;
            m = matrix;
            h = matrix.length;
            w = matrix[0].length;
            if (w == 0 || h == 0)   return false;
    
            return searchMatrix(0, 0, h - 1, w - 1, target);
        }
    
        // search sub matrix matrix[r1][c1]  ~ matirx[r2][c2].
        private boolean searchMatrix(int r1, int c1, int r2, int c2, int t) {
            if (r1 > h - 1 || r2 > h - 1 || c1 > w - 1 || c2 > w - 1) return false;
            if (t < m[r1][c1] || t > m[r2][c2]) return false;
            if (r1 > r2 || c1 > c2) return false;
            if (r1 == r2 && c2 == c1)   return m[r1][c1] == t;
    
            // split  into 4 matrix
            int cm = c1 + (c2 - c1) / 2;
            int rm = r1 + (r2 - r1) / 2;
    
            return  searchMatrix(r1, c1, rm, cm, t)     ||
                    searchMatrix(r1, cm + 1, rm, c2, t) ||
                    searchMatrix(rm + 1, c1, r2, cm, t) ||
                    searchMatrix(rm + 1, cm + 1, r2, c2, t);
        }
    

Log in to reply
 

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