m行n列

• 您是否必须要一个复杂度为O(m (log m+ log n))的解决方案？
• 我可以想到一个复杂度为O(k * log-m)的解决方案，额外的空间为O（m）
• 对于这种复杂性，可以使用修改后的PriorityQueue（heap）DataStructure

class PQObject {
    int value; // PQ sorting happens on this int..
    int m; // And m and n are positions.
    int n;
}

• 您可以将第一列中的所有值放入优先级队列，然后开始弹出，直到第k个最小的元素
• 每次弹出时，在弹出的对象中使用m和n重新插入该行的下一个值。
• 最终问题归结为在M个排序数组中找到第k个最小元素。

A recent paper by Kaplan et al给出了这个问题的最佳算法，至少从大O的Angular 来看是这样。具体来说，通过使用软堆数据结构，他们给出了在时间上运行的算法

• 当k ≤ 2m时，时间复杂度为O（m + k）;
• 对于k ≥ 2m的情形，其时间复杂度为O（m log（k/m））;和/或
• 一般来说，时间复杂度为O（m + Σ log（ni +1）），其中ni是第i行中小于或等于第k个最小项的项数。

所有这些运行时都是最优的，因为假设我们只能使用基于比较的算法，没有一个运行时可以在大O意义上得到改进。
这里涉及的算法是平凡的，但比以前的算法满足类似的时间界限简单得多。软堆数据结构的使用是使一切正确和快速工作的关键。