登录
  • #刷题
  • #二分/排序/搜索

so‌‌‍‍‌‍‍‌‍‌‍‍‌‍‍‍‍‍‌‌‍‌‌‌‍‌‍‍‌‍‌‍rted matrix搜索的高难度版本

mgccl
836
6
给一个有序矩阵, 就是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))
6条回复
热度排序

发表回复