刚刚结束的二面,给一个矩阵每行是排序过的,矩阵只有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了吧 当然用了理论上更快
是原题吗 更悲伤了…