问一道careercup150上的题# JobHunting - 待字闺中
c*g
1 楼
Given a matrix in which each row and each column is sorted, write a method
to find an element in it.
上面给的算法是,从最右上角开始找起,然后每次去掉一行或者一列。
我有如下疑问
1) 如果从左下角开始,也是对的吧,每次去掉一行或者一列;
2) 这个算法的时间复杂度应该是N*M吧?
3) 可以更加优化么? 每次找的时候,用二分发找到那个数所在的区间,就是恰好找
到一个大于它的,一个小于它的,这样时间复杂度不就是(lgM * lgN)?
to find an element in it.
上面给的算法是,从最右上角开始找起,然后每次去掉一行或者一列。
我有如下疑问
1) 如果从左下角开始,也是对的吧,每次去掉一行或者一列;
2) 这个算法的时间复杂度应该是N*M吧?
3) 可以更加优化么? 每次找的时候,用二分发找到那个数所在的区间,就是恰好找
到一个大于它的,一个小于它的,这样时间复杂度不就是(lgM * lgN)?