JAVA Solution Beat 78%


  • 0
    J
    public 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, index = 0;
            int i;
            for (i = 0; i < row; i++) {
                index = i;
                if (target <= matrix[i][col-1]) break;
            }
            
            if (i == row) return false;
            
            int start = 0, end = col - 1, mid = 0;
            while (start <= end) {
                mid = (end - start)/2 + start;
                if (matrix[index][mid] > target) end = mid - 1;
                else if (matrix[index][mid] < target) start = mid + 1;
                else return true;
            }
            
            return false;
            
        }
    }

  • 0

    I run your code but it just beats only 6.7%. Actually, I come out 3 binary search ways but all of them will use 1ms and rank 6.7%.

    Here is my solution.

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if(matrix.length<1 || matrix[0].length<1) return false;
            if (target<matrix[0][0] || target>matrix[matrix.length-1][matrix[0].length-1]) return false;
            
            int[] firstColumn = new int[matrix.length];
            for(int i=0;i<firstColumn.length;i++){
                firstColumn[i]=matrix[i][0];
            }
            
            int index = Arrays.binarySearch(firstColumn,target);
            if(index>=0) return true;
            else{
                
                int row=-index-1 -1; // -1 to go up to the target row
                return Arrays.binarySearch(matrix[row],target)>=0;
            }
        }
    }

Log in to reply
 

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