文章目錄

• • 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) 時間復雜度

/*** // 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;}elser = 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

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1428. 至少有一个 1 的最左端列（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。