algorithm - 最大化数组的最小值

Question

可能有一个有效的解决方案，但我没有看到。我不确定如何解释我的问题，但这里是...

假设我们有一个包含 n 个整数的数组，例如 {3,2,0,5,0,4,1,9,7,3}。我们要做的是找到具有“最大最小值”的5个连续元素的范围......此示例中的解决方案是这部分 {3,2,0,5,0,4,1,9,7,3}，其中 1 为最大值最低限度。

用 O(n^2) 很容易做到，但必须有更好的方法来做到这一点。这是什么？

Answer 1

如果您的意思是字面上的五个 连续元素，那么您只需要保留源数组的排序窗口。说你有:{3,2,0,5,0,1,0,4,1,9,7,3}

首先，你得到五个元素并对它们进行排序:

{3,2,0,5,0, 1,0,1,9,7,3}
{0,0,2,3,5} - 已排序。

这里最小值是排序序列的第一个元素。

然后你需要向右前进一步，你会看到新元素1和旧元素3，你需要找到并替换 3 与 1 然后将数组返回到排序后的状态。您实际上不需要对其运行排序算法，但您可以这样做，因为只有一个元素位于错误的位置(本例中为 1)。但即使是冒泡排序也会在线性时间内完成。

{3,2,0,5,0,1, 0,4,1,9,7,3}
{0,0,1,2,5}

然后新的最小值再次成为第一个元素。

然后一次又一次地推进并将排序序列的第一个元素与最小值进行比较，并记住它和子序列。

时间复杂度为 O(n)。