从k个未排序数组各选元素最小化极值差，求O(nk)/O(nlogk)算法

给定k个未排序数组，所有数组的元素总数为n。我们需要从每个数组中恰好选择一个元素组成集合A，目标是最小化集合A中最大值与最小值的差值。

我认为该问题无法在O(klogn)的时间复杂度内解决，因为最坏情况下至少需要遍历一次输入，因此时间复杂度不可能低于O(n)。另外，当数组已排序时，对应算法的时间复杂度为O(nlogk)。请问是否存在时间复杂度为O(nk)或O(nlogk)的算法？

时间复杂度下限确认 #

你判断的没错，这个问题的时间复杂度下限确实是**O(n)**——因为必须遍历所有元素才能确保不遗漏最优的候选组合，所以任何正确的算法都不可能比这个复杂度更快。

针对未排序数组的可行算法分析 #

1. 复杂度接近O(nk)的实用解法

   • 首先对每个子数组单独排序，总时间为O(n log m_i)（m_i为第i个数组的元素数量），整体等价于O(n log n)（每个元素都参与一次排序操作）。
   • 排序完成后，问题就转化为「k个有序数组中各选一个元素，最小化最大值与最小值的差」，这个问题可以用O(n log k)的算法解决：用优先队列维护当前选中元素的窗口，通过移动各数组的指针来逐步收缩差值，找到最优解。
   • 如果不做预排序，直接暴力枚举所有可能的元素组合，时间复杂度会是O(∏m_i)，这远高于O(nk)，完全不具备实用性。而先排序再用有序数组解法的总复杂度是O(n log n + n log k)，当k远小于n时，这个复杂度比O(nk)更优。

2. 是否存在O(nlogk)的严格最优算法？

   • 不存在。因为处理未排序数组时，必须先将每个子数组转化为有序结构（排序是最直接的方式），这一步的时间开销已经是O(n log (n/k))（假设数组平均大小为n/k），这已经高于O(nlogk)。只有当输入数组本身就是有序的，才能达到O(nlogk)的复杂度。

3. 特殊场景下的优化思路

   • 如果允许接受近似解，可以通过随机采样每个数组的部分元素来减少排序开销，但如果要求严格的最优解，就必须完成每个子数组的有序化处理，无法绕过这部分时间成本。

内容的提问来源于stack exchange，提问作者ErroR