関小君刷题记

题目大意：

（这是一道互动问题）

二进制矩阵的定义是它的所有元素不是0就是1。另外矩阵的每一行上的元素都是按照非递减顺序排列。

给定一个每一行都排序好的二进制矩阵，请你返回包含1的最靠左一列的下标。如果不存在这样的列，返回-1。

你不能直接访问二进制矩阵。你只能通过BinaryMatrix 类的接口访问二进制矩阵。

• BinaryMatrix.get(row, col) 返回第row行第col列上的元素。（0-based）
• BinaryMatrix.dimensions() 返回一个列表[rows, cols]，代表矩阵拥有rows行以及cols列。

你不能调用BinaryMatrix.get方法超过1000次，否则会被判定为错误答案。

Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

• rows == mat.length
• cols == mat[i].length
• 1 <= rows, cols <= 100
• mat[i][j] is either 0 or 1.
• mat[i] is sorted in a non-decreasing way.

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1428

解题思路分析：

这道题最简单粗暴的方式就是查看每一个点上的数字，然后找到一个数值是1并且列数最小的返回即可。不过题目中明确说明BinaryMatrix.get(row, col)这个方法不能使用太多次，那么我们只能想办法优化算法。对于本题，由于每一行上的数字已经按照升序排列，因此我们可以通过二分查找的方法找到每一行上第一个大于等于1的数字。对于这个二分查找的思路，可以参考我之前总结过的文章：LEETCODE常见算法之二分查找超详细白话讲解，其中第二个例子就是本题的模板。在找到每一行中第一个1所在的列位置之后，我们只要找到一个最小列即是本题的结果。

使用二分查找的解题方式的时间复杂度是O(rows*log cols)，其中rows为矩阵行数，cols为列数。

实现代码：

int rows, cols;
public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
    List<Integer> list = binaryMatrix.dimensions();
    rows=list.get(0);
    cols=list.get(1);
    int minCol=cols;
    for(int row=0;row<rows;row++){
        minCol=Math.min(minCol,findFirstOne(binaryMatrix,row));
    }
    return minCol==cols?-1:minCol;
}

int findFirstOne(BinaryMatrix binaryMatrix, int row){
    int low=0,high=cols-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(binaryMatrix.get(row,mid)==1){
            high=mid-1;
        }else{
            low=mid+1;
        }
    }
    return low;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Leftmost Column with at Least a One.

Memory Usage: 40 MB, less than 100.00% of Java online submissions for Leftmost Column with at Least a One.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1428-leftmost-column-with-at-least-a-one-解题思路分析/