TL;DR 我认为这不可能以O(n)
的时间复杂度实现(虽然我无法证明),因此以下是两个O(n*logk)
解决方案。
解决方案1:使用大小为k
的小根堆,如这里所述。
解决方案2:(我的)
我们需要三个额外的数组,称它们为A
、B
和C
。我们也将输入数组称为“原始数组”。
A
的大小将为 n
,并将保持所有原始数组中的元素按排序顺序排列
B
也将具有大小 n
,并将保留有关数组 A
中元素来源的信息,即来自哪个原始数组元素在 A
中
C
将具有大小 k
,并且它将包含在过程中从原始数组中看到的元素的最后一个索引(见下文)
因为原始数组已经排序,我们可以使用
k-way merge algorithm(例如使用min-heap:在开始时将所有原始数组的第一个元素放入min heap中;然后迭代地从min heap中弹出最小的元素,将其放入
B
中,并将相同原始数组的下一个元素推入堆中)在
O(n*logk)
时间内创建数组
A
和
B
。因此,对于您提供的示例,数组
A
和
B
如下所示:
A = [5, 6, 7, 11, 18],B = [1, 2, 1, 0, 2]
(
5
来自第二个原始数组,
6
来自第三个原始数组等)。
现在我们使用
滑动窗口技术来找到大小至少为
k
的窗口,其最后一个元素和第一个元素之间的差异最小。这个想法是遍历数组
B
,直到我们从
所有原始数组中“收集”元素 - 这意味着我们找到了一种组合,现在只需检查该组合的第一个和最后一个元素之间的差异即可。现在数组
C
进入游戏 - 我们将其所有元素初始化为-1,并将
C[i]
设置为原始数组
i
中任何元素的最后索引。一旦我们找到第一个包含所有原始数组元素的滑动窗口,我们进一步向右扩展该窗口,并从左缩小,同时保持所有原始数组的代表都在窗口内。因此,算法如下所示:
int collected = 0;
int min_idx = 0;
int result = INT_MAX;
for (int i = 0; i < n; ++i) {
bool check_result = false;
if (C[B[i]] == -1) {
++collected;
check_result = true;
}
C[B[i]] = i;
while (min_idx < C[B[min_idx]] && min_idx < i) {
check_result = true;
++min_idx;
}
if (collected < k) continue;
if (check_result && result > (A[i] - A[min_idx]))
result = (A[i] - A[min_idx]);
}
return result;
让我们通过你的例子来解释它:
A = [5, 6, 7, 11, 18]
B = [1, 2, 1, 0, 2]
C = [-1, -1, -1]
i = 0 // state after step 0, we have seen element from array 1
min_idx = 0
C = [-1, 0, -1]
collected = 1
result = INT_MAX
i = 1 // we have seen element from array 2
min_idx = 0
C = [-1, 0, 1]
collected = 2
result = INT_MAX
i = 2 // again element from array 1, increase min_idx
min_idx = 1
C = [-1, 2, 1]
collected = 2
result = INT_MAX
i = 3 // element from array 0, window is full, update result
min_idx = 1
C = [3, 2, 1]
collected = 3
result = 5
i = 4 // again element from array 2, increase min_idx and compare with result -> it is bigger, so don't update result
min_idx = 2
C = [3, 2, 4]
collected = 3
result = 5
时间复杂度为
O(n*logk)
,因为从
k
个排序数组创建数组
A
和
B
需要
O(n*logk)
,在循环期间,每个
n
元素最多被检查两次,所以这部分是
O(n)
,最后
O(n*logk + n) = O(n*logk)
。如果将原始数组合并为一个数组,则
这是您可以获得的最佳效果:
可以证明,不存在基于比较的k路归并算法,其运行时间为O(n f(k)),其中f增长速度比对数函数慢。
希望这可以帮到您!
k
是否为常数。如果k
是某个小的或者常数级别的数字,那么k*n
或(logk)*n
仍然是O(n)
。 - Asad Saeeduddin