这样的面试题，你会吗？（有奖）

hbmhalley

回复 34# pozenfly


    [1] 这个题的单调性很干净么? 如何二分?

hbmhalley

回复 32# cjaizss


    如果不顺着找 就必须充分利用信息 也就是单调性
    一维的时候 二分所能利用到的信息是：对于某个mid，若num<a[mid]，则任意r>mid都满足num<a[r]；对称类似。
    二位的时候 如果单拿出某一个数 可以确定左上与右下blabla 但二维的单调性不干净，左下与右上不好处理 一旦将左下与右上作为子问题，复杂度必然不低于O(row+coloum)
    22L利用到的信息也算挺多的了

cjaizss

回复  cjaizss


    如果不顺着找 就必须充分利用信息 也就是单调性
    一维的时候 二分所能利用到的 ...
hbmhalley 发表于 2011-12-06 01:26

    这个问题本来就是一个NL问题,居然给出一个线形算法.....
    两次二分就可以了,或者像之前那个兄弟那样,整体二分

hellozhouke

回复 22# crazyhadoop


    确实是懂得流程比写代码重要。

pozenfly

回复 41# hbmhalley


    童鞋！ 首先你要搞清楚，不管几围数组在内存里面都是一围数组（比如：C,PASCAL里面是行优先，FORTRAN里面是列优先），所以如果是C语言的话，直接把这个二围数组当作0 到 N*M-1的一围数组，那么效率是：O(log(N*M)).
但是这里的行列都是严格递增的，可以通过二分确定要找的数在哪一行（二分比较时，同时比较每行第一个和最后一个），然后再在所在行二分，这不就是我上面所说的复杂度么？
另外，如果要在同一个表中平凡查找不同的数，表中数字范围不大内存允许的话，可以做一个BIT MAP的哈稀，这样查询时间就为O(1)了

tjpulord

1. 数组安列二分查找，找到返回true，否则返回最大的小于该数的数所在的行数。从此行开始递减，利用二分查找每行中是否存在，若找到返回true，否则递减一行继续二分查找，直到第0行，若没有找到，返回false

2. 斐波那契数列，只是第一项f(1)=1, f(2)=2, f(n)=f(n-1)+f(n-2)。
代码略

hbmhalley

回复 44# pozenfly


    您说的这两个其实是一个东西，而且显然log(m*n)==log(m)+log(n)
    但我不懂 这个二维数组在内存中是线性存储这不假，但这个线性数组是单调的么？
    换句话说，设题目中这个数组是a[][4],那么你在初始化的时候不应该是{1,2,8,9,2,4,9,12,...}这样么？这不单调啊
    或者您贴出来一份代码 谢谢

hbmhalley

回复 42# cjaizss


    如何二分？
    如果是"2"分，那么单调性何在？
    如果是"4"分，那么可以构造一组这样的数据：
    设以下形状的矩阵是X矩阵：
        C1 C2
        C3 C4
    满足：1)这个矩阵满足题目条件 2)四个矩阵均为(2^k)*(2^k)方阵 3)C2 C3互为转置 4) C2 C3均为X矩阵
    要满足这个很简单，只要C1=0, C4=INF

    意思就是 1)这种矩阵可以方便地构造，当然不一定如此极端，C2 C3也可以有微小差距 2) 在这种矩阵中，C2 C3差距很小，如果是四分 很难处理其中的“单调性” 一旦将其作为子问题处理 必然有 f(n) = 2*f(n/2) + 1，不低于线性.

cjaizss

回复  cjaizss


    如何二分？
    如果是"2"分，那么单调性何在？
    如果是"4"分，那么可以构造 ...
hbmhalley 发表于 2011-12-06 11:03

  这里,二分只是随意叫的一个词汇,别当真,其实就是跟线性二分一样,对数级查找
两次线性很容易,横一次,再竖一次,就查到了
单调性在于:
a[x][y]
a[X][Y]
如果x>=X,y>=Y
则
a[x][y]>=
a[X][Y]

hbmhalley

回复 48# cjaizss


    对角线么？有用么？还是贴代码吧.