0 ms Java


  • 0
    K

    This could probably be cleaned up a little bit but it seems to run very fast. It divides the array of arrays til if finds the one containing the number. Then divides the values in the arrays until it finds the value it wants.

    public class Solution {
     public boolean searchMatrix(int[][] matrix, int target) {
    	        
    		 int matrixIndex = whichMatrix(0, matrix.length-1,matrix, target);
    		 if(matrixIndex!=-1){
    			 int indexInRow = findIndexInRow(0, matrix[matrixIndex].length-1, matrix[matrixIndex], target);
    			 return indexInRow>-1;
    		 }
    		 return false;
    	  }
    	 
    	/**
    	 * Search for the correct row in the matrix.
    	 * @param matrix
    	 * @param target
    	 * @return index if it is available, -1 if not found
    	 */
    	 public int whichMatrix(int start, int end, int[][] matrix, int target){
    		 if(end - start <= 1){
    			 if(matrix[end][matrix[end].length-1]>=target) {
    				 if(matrix[end][0]<=target){
    					 return end;
    				 }
    			 } 
    			 if( matrix[start][matrix[start].length-1]>=target){
    				 if(matrix[start][0]<=target){
    					 return start;
    				 }
    				 
    			 }
    			 return -1;
    		 }
    		 int mid = (end + start)/2;
    		 if(matrix[mid][0]>target) return whichMatrix(start, mid, matrix, target);
    		 if(matrix[mid][matrix[mid].length-1]<target) return whichMatrix(mid, end, matrix, target);
    		 return mid;
    
    	 }
    	 
    	 public int findIndexInRow(int start, int end, int[] nums, int target){
    		 if(end - start <=1){
    				if(nums[start]==target){
    					return start;
    				} else if(nums[end]== target){
    					return end;
    				}
    			}else{
    				int mid = (end + start)/2;
    				if(nums[mid]<target) return findIndexInRow(mid, end, nums, target);
    				if(nums[mid]>target) return findIndexInRow(start, mid, nums, target);
    				if(nums[mid]==target) return mid;
    			}
    			return -1;
    		 
    	 }
    	 
    	 
    }
    

Log in to reply
 

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