Image there is robot loaded with Google map data, we can use this algorithm to direct the robot to quickly find the hill in any given square in the map.
Time complexity: O(num_rows * lg (num_cols) )
public static int[] findPeakIn2DMatrix(int[][] matrix){
int rows = matrix.length;
int cols = matrix[0].length;
int start = 0, end = cols -1;
int maxIndex = 0; int mid = 0;
while(start<=end){
mid = (start+end)>>>1;
maxIndex = 0;
for(int i=1; i<rows; i++)
maxIndex = matrix[i][mid]>matrix[maxIndex][mid]?i:maxIndex;
if(mid-1>=0 && matrix[maxIndex][mid-1]>matrix[maxIndex][mid])
end = mid-1;
else if(mid+1<cols && matrix[maxIndex][mid+1]>matrix[maxIndex][mid])
start = mid+1;
else
break;
}
return new int[]{maxIndex, mid};
}
No comments:
Post a Comment