vs2010 c 建设网站,昆明凡科建站,wordpress怎么改图标,目前最流行的拓客方法文章目录1. 题目2. 解题2.1 二分查找2.2 直接走阶梯1. 题目
#xff08;这是一个交互题#xff09;
我们称只包含元素 0 或 1 的矩阵为二进制矩阵。 矩阵中每个单独的行都按非递减顺序排序。
给定一个这样的二进制矩阵#xff0c;返回至少包含一个 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 BinaryMatrixs API interface.* // You should not implement it, or speculate about its implementation* class BinaryMatrix {* public:* int get(int row, int col);* vectorint 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(mv0)l mid1;else{if(mid0 || binaryMatrix.get(i,mid-1)0){left1col min(left1col, mid);break;}elser mid-1;}}if(left1col0)break;}return left1colINT_MAX ? -1 : left1col;}
};12 ms 8.3 MB
2.2 直接走阶梯
在右下角或者右上角开始出发遇到0竖向走遇到1往左走Omn时间复杂度
/*** // This is the BinaryMatrixs API interface.* // You should not implement it, or speculate about its implementation* class BinaryMatrix {* public:* int get(int row, int col);* vectorint 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(cur0)i--;//遇到0往上走else//遇到1{left1col min(left1col, j);j--;//遇到1往左走}if(left1col0)break;}return left1colINT_MAX ? -1 : left1col;}
};8 ms 8.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
