我有log n行，每行包含n个数。
我希望在所有行中的每个位置找到最小值：
[1, 2, 3, 4, 5, 6, 7, 8]
[2, 3, 4, 1, 2, 3, 4, 5]
[3, 6, 7, 8, 3, 4, 1, 2]
[9, 7, 2, 3, 2, 1, 3, 1]
应该产生如下数组：
[1, 2, 2, 1, 2, 1, 1, 1]
我很容易在
O(nlogn)时间内使用蛮力方法我甚至可以看到一个分而治之的解决方案，它将行分成两半，并在每一侧递归地运行算法，这将花费
O(nloglogn)时间。但我看不到删除
n的方法在我看来，我至少需要看一次每一行中的每一个位置。有没有办法让复杂性变小？
最佳答案
如果X大小的数组没有以某种已知的特殊方式进行排序或构造，则在其中查找元素y的成本必须等于X，因为不能跳过X中的任何元素（跳过的元素可以是解决方案）。
搜索顺序也不重要。如果您将其拆分并进行分而治之等操作，那么元素y仍然可以是您最后访问的元素。
因此，如果有一个大小数组n*logn，那么最低可能的复杂性是Omega(n* log n)。
关于algorithm - 在每一列中查找最小值的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34064291/