文章目录
1. 题目2. 解题2.1 二分查找2.2 直接走阶梯
1. 题目
（这是一个交互题）
我们称只包含元素 0 或 1 的矩阵为二进制矩阵。 矩阵中每个单独的行都按非递减顺序排序。
给定一个这样的二进制矩阵，返回至少包含一个 1 的最左端列的索引（从 0 开始）。 如果这样的列不存在，返回 -1。
您不能直接访问该二进制矩阵。 你只可以通过 BinaryMatrix 接口来访问。
BinaryMatrix.get(row, col) 返回位于索引 (row, col) （从 0 开始）的元素。BinaryMatrix.dimensions() 返回含有 2 个元素的列表 [rows, cols]，表示这是一个 rows * cols的矩阵。
如果提交的答案调用 BinaryMatrix.get 超过 1000 次，则该答案会被判定为错误答案。提交任何试图规避判定机制的答案将会被取消资格。
下列示例中， mat 为给定的二进制矩阵。您不能直接访问该矩阵。
示例 1:
输入
: mat
= [[0,0],[1,1]]
输出
: 0
示例 2:
输入
: mat
= [[0,0],[0,1]]
输出
: 1
示例 3:
输入
: mat
= [[0,0],[0,0]]
输出
: -1
示例 4:
输入
: mat
= [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
输出
: 1
提示
:
rows
== mat
.length
cols
== mat
[i
].length
1 <= rows
, cols
<= 100
mat
[i
][j
] 只会是
0 或
1。
mat
[i
] 已按非递减顺序排序。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/leftmost-column-with-at-least-a-one 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 二分查找
对每一行进行二分查找，查找最左侧的1的位置，O(m log n) 时间复杂度
class Solution {
public:
int leftMostColumnWithOne(BinaryMatrix
&binaryMatrix
) {
int m
, n
, i
, j
, left1col
= INT_MAX
, l
, r
, mid
, mv
;
auto dim
= binaryMatrix
.dimensions();
m
= dim
[0], n
= dim
[1];
for(i
= 0; i
< m
; ++i
)
{
l
= 0, r
= n
-1;
while(l
<= r
)
{
mid
= l
+((r
-l
)>>1);
mv
= binaryMatrix
.get(i
, mid
);
if(mv
==0)
l
= mid
+1;
else
{
if(mid
==0 || binaryMatrix
.get(i
,mid
-1)==0)
{
left1col
= min(left1col
, mid
);
break;
}
else
r
= mid
-1;
}
}
if(left1col
==0)
break;
}
return left1col
==INT_MAX
? -1 : left1col
;
}
};
12 ms 8.3 MB
2.2 直接走阶梯
在右下角或者右上角，开始出发，遇到0竖向走，遇到1往左走，O（m+n）时间复杂度
class Solution {
public:
int leftMostColumnWithOne(BinaryMatrix
&binaryMatrix
) {
int m
, n
, i
, j
, left1col
= INT_MAX
, cur
;
auto dim
= binaryMatrix
.dimensions();
m
= dim
[0], n
= dim
[1];
i
= m
-1, j
= n
-1;
while(i
>= 0 && j
>= 0)
{
cur
= binaryMatrix
.get(i
,j
);
if(cur
==0)
i
--;
else
{
left1col
= min(left1col
, j
);
j
--;
}
if(left1col
==0)
break;
}
return left1col
==INT_MAX
? -1 : left1col
;
}
};
8 ms 8.2 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
