/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* class BinaryMatrix {
* public:
* int get(int row, int col);
* vector<int> dimensions();
* };
*/
class Solution {
public:
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
}
};
/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* type BinaryMatrix struct {
* Get func(int, int) int
* Dimensions func() []int
* }
*/
func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
last := binaryMatrix.Dimensions()
h,w := last[0]-1, last[1]-1
var find bool
for w>=0 && h>=0{
if binaryMatrix.Get(h,w)==1{
find = true
w--
}else{
h--
}
}
if !find{
return -1
}
return w+1
}
/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* type BinaryMatrix struct {
* Get func(int, int) int
* Dimensions func() []int
* }
*/
func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
group := binaryMatrix.Dimensions()
rows, cols := group[0], group[1]
l := make([]int, 0, rows)
for row:=0; row<rows; row++ {
if binaryMatrix.Get(row, cols-1) == 1 {
l = append(l, row)
}
}
if len(l) ==0 {
return -1
}
min := cols-1
for _,row:=range l {
m := midSearch(binaryMatrix, row, 0, min)
if m < min {
min = m
}
}
return min
}
func midSearch(b BinaryMatrix, row, start, end int) int {
if start == end {
return start
}
if b.Get(row, (start+end)/2) == 1 {
return midSearch(b, row, start, (start+end)/2)
} else {
return midSearch(b, row, (start+end)/2 +1, end)
}
}
/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* class BinaryMatrix {
* public:
* int get(int row, int col);
* vector<int> dimensions();
* };
*/
class Solution {
public:
// 利用单调递增性质，从右下到左上遍历，从右边遇到第一个为0的位置pos， 则pos左侧一定全为0
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
int m = binaryMatrix.dimensions()[0], n = binaryMatrix.dimensions()[1];
int ans = n, i = m - 1, j = n - 1;
while (i >= 0 && j >= 0) {
while (j >= 0 && binaryMatrix.get(i, j)) j--;
i--;
}
return j == n - 1 ? -1 : j + 1; // j = n - 1时，表示元素全部为0
}
};
/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* class BinaryMatrix {
* public:
* int get(int row, int col);
* vector<int> dimensions();
* };
*/
class Solution {
public:
// 二分法、对每一行进行二分，
int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
int m = binaryMatrix.dimensions()[0], n = binaryMatrix.dimensions()[1];
int ans = n;
for (int i = 0; i < m; i++) {
int left = 0, right = n, mid;
while (left < right) { // 找到第一个1的位置
mid = (left + right) >> 1;
if (binaryMatrix.get(i, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
if (left < n) ans = min(ans, left); // left = n时表示该行中不存在1
}
return ans == n ? -1 : ans;
}
};
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
# def get(self, row: int, col: int) -> int:
# def dimensions(self) -> list[]:
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
row, col = binaryMatrix.dimensions()
i, j = 0, col - 1
while -1 < i < row and -1 < j < col:
if binaryMatrix.get(i, j) == 1:
j -= 1
else:
i += 1
if j == col - 1:
return -1
else:
return j + 1
/**
* // 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) {
List<Integer> d = binaryMatrix.dimensions();
int r = d.get(0) - 1;
int c = d.get(1) - 1;
int ans = -1;
while (r >= 0){
if (binaryMatrix.get(r, c) == 1) {
if (c == 0) return 0;
ans = c;
c --;
}
else r--;
}
return ans;
}
}
