LeetCode 1428. 至少有一个 1 的最左端列（二分查找）

Michael阿明

发布于 2020-07-13 14:48:57

8070

发布于 2020-07-13 14:48:57

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

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) 时间复杂度

/**
 * // 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, 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）时间复杂度

/**
 * // 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, 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--;//遇到0往上走
            else//遇到1
            {
                left1col = min(left1col, j);
                j--;//遇到1往左走
            }
            if(left1col==0)
                break;
        }
        return left1col==INT_MAX ? -1 : left1col;
    }
};

8 ms 8.2 MB

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-07-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dimensions