FindLeftMost1inMatrix

给一个矩阵

类似这样的

[[0, 0, 1, 1, 1],

[0, 1, 1, 1, 1],

[0, 0, 1, 1, 1],

[0, 0, 0, 0, 0],

[0, 0, 0, 1, 1]]

1. 每一个cell 要不是0 要不是1

2. 每一行只要发现一个1， 剩下的都是1

3. 这个数组是正方形的

问题：找到最左边的有1的列

     * 最优法复杂度O(m + n) (), m是行，n是列
     * 从右上角开始(i,j)，如果当前元素是1并且(i,j-1)也是1，那么就左移走到(i,j-1);
     *      否则，往下走到(i+1,j)
     * 重复这个操作，直到i==m
     * 最后return j

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#include "misc.h" class Solution{ public: int getLeftMost1(vector<vector<int>>& matrix){ int m = matrix.size(), n = matrix[0].size(); int i = 0, j = n-1; while(i<m && j>=0){ if(j-1>=0 && matrix[i][j-1]==1){ j--; }else if(i+1<m){ i++; }else{ break; } } return j; } }; int main(){ vector<vector<int>> matrix{{0, 0, 1, 1, 1},{0, 0, 1, 1, 1},{0, 0, 1, 1, 1},{0, 0, 0, 0, 0},{0, 0, 0, 1, 1}}; Solution sol; cout<<sol.getLeftMost1(matrix)<<endl; return 0; }

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=501860