sorted matrix搜索的高难度版本

给一个有序矩阵, 就是M[i,j]<=M[i,j+1], M[i,j]<=M[i+1,j].
测试x是否存在于矩阵里.

h: <=x的数字所组成的staircase shape有多少个steps.
k: <=x的数字有多少个.
n: <=x的数字所组成的staircase shape可以放在一个nxk的矩阵里或者kxn的矩阵里.

比如这个图形里, h是5.

h,n,k都不是事先知道的.


1.
x是给定的, 可以使用的.
算法能达到O(h log k)就可以了.
O(h log(k/h))更好
O(h log(k/h^2))不期望面试时做出来.

2.
并不给x, 但是给一个函数f, 使得f(y)返回是否y<=x.
要求, 使用f最多O(log(k))次.

复杂度O(n log k)就很好, 当然O(n log(k/n))就更好了.


实际上引出一个未解问题.
能否第二个问题里, 复杂度也是O(h log(k/h^2))

说几个观察：

• 横向的查找采用小于等于查找，竖向采用大于等于查找。
• 总体复杂度最坏应该是 h * log K.  但是期望应该是 h log （sqrt(K)）。和楼主的O(h log(k/h))搭配不上。这点想不明白。
• 第二问既然有此函数：使得f(y)返回是否y<=x，那么对其使用f最多O(log(range（matrix max - matrix min）))次，就可以求得x的值。
  

14417335 发表于 2019-3-2 22:10
说几个观察：

横向的查找采用小于等于查找，竖向采用大于等于查找。

总体复杂度最坏应该是 h * log ...

用exponential search而不是binary search可以得到O(h log k/h)

获得O(h log(k/h^2))需要证明下面的
有数字0=k_1<=k_2<=... <=k_h = k.
则sum log(k_{i+1}-k_i) 是O(h log(k/h^2))

补充内容 (2019-3-4 07:01):
少了个条件sum k_i = k. 还有不存在k_h=k这个条件

步惊云 发表于 2019-3-4 11:01
你写的真的很乱, 我很多地方只能靠猜. 想写题你就明明白白写的好一点, 例子举好一点.

看来看去还是不理 ...

题意是原来问题, 不要看后面回复.

可能看这个问题比较容易理解题意. https://cstheory.stackexchange.c ... -in-a-sorted-matrix   (那问题里有不一样的变量名)

有另一个paper达到同样的时间. http://mediatum.ub.tum.de/doc/1094388/TUM-I0821.pdf
我个人觉得这个人的算法比较难懂.

https://arxiv.org/pdf/1711.00599.pdf
这里面的Lemma 2.1 是为了解决另一个问题的, 但算法是一样的.
大概给的是如果h=w, 如何用log w query找到x.
h和w差距很大弄到h log (w/h) 就要用其他方法, 可以看Lemma 2.1前面cite的那些文章. 方法区别不大.