如何在m*n矩阵中找到每行(M)按O(m(log +log ))排序的第k个元素？

Question

假设我们有一个m*n矩阵，每行都是按顺序排列的。所以，我只知道这个问题的最佳算法的阶数是O(m(log + log ))。(这是一个测试题，结果是这样的)但是我不知道这个算法是如何工作的

Answer 1

一个想法可以是这样的。

如果我问你，给定的数x在原始矩阵中的秩是多少？你如何回答这个问题？一个答案可以是：

只需对每行中x或更大元素的第一个匹配项进行二进制搜索。然后添加个人排名。

int rank = 1;
for (int i = 0; i < m; ++i) {
    rank += std::lower_bound(matrix[i].begin(), matrix[i].end(), x);
}

这可以在O(m * log )时间内完成(对n个大小的数组进行m个二进制搜索)。

现在我们只需要对x进行二进制搜索(在0和INT_MAX或matrix[0][k]之间)来找到第k个等级。由于INT_MAX是常数的，所以理论上总体时间复杂度为O(m * log )。一种优化可以使用智能范围代替matrix[i].begin(), matrix[i].end()来完成。

PS：仍在考虑O(m*(log m + log n))或O( m * (log mn))解决方案。