首页 > 试题广场 >

设 A[0, n)[0, n)为整数矩阵(即二维向量),A[

[问答题]
设 A[0, n)[0, n)为整数矩阵(即二维向量),A[0][0] = 0 且任何一行(列)都严格递增。
a) 试设计一个算法,对于任一整数 x ³ 0,在 O(r + s + logn)时间内,从该矩阵中找出并报告所有值为 x 的元素(的位置),其中 A[0][r](A[s][0])为第 0 行(列)中不大于 x 的最大者;(提示:马鞍查找(saddleback search))
b) 若 A 的各行(列)只是非减(而与是严格递增),你的算法需做何调整?复杂度有何发化?

这道题你会答吗?花几分钟告诉大家答案吧!