05 August 2008
一个行排序的01矩阵，行排序表示每一行是非递减顺序，只能调用给定的api，BinaryMatrix.get(row, col)返回某个值，BinaryMatrix.dimensions()返回整个matrix的维度
求最左边的含有1的列的index（从0开始）
将二维数组转换为一维来处理，然后二分
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
37
38
39
40
41
/**
* // 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 {
/**
* 1. binaryMatrix.demensions() to return rows and cols
* 2. convert rows * cols to cordinates, start from col 0 - [0,0][1,0][2,0]: len = rows * cols - 1, if len % cols == 0, col 0..., put all cols elements into a array (len rows)
* 3. binary search from col 0, until find the first col which contains 1
*/
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
int rows = binaryMatrix.dimensions().get(0);
int cols = binaryMatrix.dimensions().get(1);
// System.out.println(rows);
int leftMostIndex = Integer.MAX_VALUE;
for (int i = 0; i < rows; i++) {
int left = 0, right = cols - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2; // mid element of one row
if (binaryMatrix.get(i, mid) == 0) { // one the right
left = mid;
} else { // itself or on the left
right = mid;
}
}
if (binaryMatrix.get(i, left) == 1) {
leftMostIndex = Math.min(leftMostIndex, left);
} else if (binaryMatrix.get(i, right) == 1) {
leftMostIndex = Math.min(leftMostIndex, right);
}
}
return leftMostIndex == Integer.MAX_VALUE ? -1 : leftMostIndex;
}
}