A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.
Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.
You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:
BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
BinaryMatrix.dimensions() returns the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols.
https://leetcode.com/problems/leftmost-column-with-at-least-a-one/description/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/** * // This is the BinaryMatrix's API interface. * // You should not implement it, or speculate about its implementation * interface BinaryMatrix { * public int get(int row, int col) {} * public List<Integer> dimensions {} * }; */ class Solution { public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) { //Get the dimension of the binary matrix List<Integer> dim = binaryMatrix.dimensions(); int cols = dim.get(1); int rows = dim.get(0); int c = cols; for(int i=0;i<rows;i++){ //search for the leftmost column with value 1 int d = binarySearch(binaryMatrix, i, 0, c-1); c = Math.min(d, c); } return c!=cols?c:-1; } private int binarySearch(BinaryMatrix binaryMatrix, int row, int lo, int hi){ while(lo < hi){ int mid = lo + (hi - lo)/2; if(binaryMatrix.get(row, mid) == 1){ hi = mid; } else { lo = mid+1; } } return binaryMatrix.get(row, lo)==1?lo:Integer.MAX_VALUE; } } |