Leftmost 1 of 01 Matrix
面经高频,给一个01矩阵,找最左边的1,给的矩阵1是连续右对齐的。http://www.1point3acres.com/bbs/thread-310963-1-1.html
例如
000000
001111
011111
000011
最左边的1在第二列.
一个矩阵有0 和 1, 1的右边一定是1, 要找到整个矩阵最左边的1。 要求复杂度比O(mn) 好。 一开始naive了, 说每行binary search。 他问能不能更好。 才发现从右上角第一个1开始往左找, 遇到0 往下找下一个1, 直到不能走了为止。 复杂度O(m + n)
解法大致上是从右上角开始,遇到0向下,遇到1向左?