|
2 | 2 | * // This is the BinaryMatrix's API interface. |
3 | 3 | * // You should not implement it, or speculate about its implementation |
4 | 4 | * interface BinaryMatrix { |
5 | | - * public int get(intx, inty) {} |
| 5 | + * public int get(introw, intcol) {} |
6 | 6 | * public List<Integer> dimensions {} |
7 | 7 | * }; |
8 | 8 | */ |
9 | 9 |
|
10 | 10 | classSolution { |
11 | 11 | publicintleftMostColumnWithOne(BinaryMatrixbinaryMatrix) { |
12 | | -List<Integer>dims =binaryMatrix.dimensions(); |
13 | | -introws =dims.get(0); |
14 | | -intcols =dims.get(1); |
15 | | -intminIdx =Integer.MAX_VALUE; |
16 | | -for (inti =0;i <rows;i++) { |
17 | | -intidx =binarySearch(binaryMatrix,i,0,cols -1); |
18 | | -if (idx != -1) { |
19 | | -minIdx =Math.min(minIdx,idx); |
| 12 | +List<Integer>dimension =binaryMatrix.dimensions(); |
| 13 | +intnumRows =dimension.get(0); |
| 14 | +intnumCols =dimension.get(1); |
| 15 | +intcurrRow =0; |
| 16 | +intcurrCol =numCols -1; |
| 17 | +while (currRow <numRows &&currCol >=0) { |
| 18 | +if (binaryMatrix.get(currRow,currCol) ==0) { |
| 19 | +currRow++; |
| 20 | + }else { |
| 21 | +currCol--; |
20 | 22 | } |
21 | 23 | } |
22 | | -returnminIdx ==Integer.MAX_VALUE ? -1 :minIdx; |
23 | | - } |
24 | | - |
25 | | -privateintbinarySearch(BinaryMatrixbinaryMatrix,introw,intstart,intend) { |
26 | | -intminIdx =Integer.MAX_VALUE; |
27 | | -while (start <=end) { |
28 | | -intmid = (start +end) /2; |
29 | | -if (binaryMatrix.get(row,mid) ==1) { |
30 | | -minIdx =Math.min(minIdx,mid); |
31 | | -end =mid -1; |
32 | | - } |
33 | | -else { |
34 | | -start =mid +1; |
35 | | - } |
36 | | - } |
37 | | -returnminIdx ==Integer.MAX_VALUE ? -1 :minIdx; |
| 24 | +returncurrCol ==numCols -1 ? -1 :currCol +1; |
38 | 25 | } |
39 | 26 | } |