脸书二面挂经

刚刚结束的二面,给一个矩阵每行是排序过的,矩阵只有0,1,找小的列,该列包含元素1,让实现O(m+n)的方法
一道题讲完就45分钟,估计跪了

按行搜索,如果最后一个元素不是1直接continue,如果是1,用binary search找该行leftmost index,下一行从index -1的位置从右往左扫,如果是index - 1的位置是0,扫下一行,不是0,找该行的leftmost

感觉有点tricky,lz是怎么做的?

对每个二分查找。 或者从矩阵右上角出发,碰到1往左边走,碰到0就往下走

什么是找小的列呀

看了回复感觉就是lintcode的原题呀

找小的列是说0最多的?

最左边的列下标

不需要binary search就可以m+n了吧 当然用了理论上更快

是原题吗 更悲伤了…