gpt4 book ai didi

algorithm - 找到每个可能子集的第 k 个最小总和

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:32:43 25 4
gpt4 key购买 nike


上次我发现了一个有趣的问题,然后就卡住了。

给定 n 个数字 a[1], ..., a[n] 按升序和数字 k (1 <= n,k <= 10^5)。

假设我们正在按总和对给定序列的每个可能子集进行排序。
我们必须找到第 k 个这样的子集的总和。

例如:
n = 4, k = 8
a = { 2, 7, 8, 15 }

1: { 2 }, 总和 = 2
2: { 7 }, 总和 = 7
3: { 8 }, 总和 = 8
4: { 2, 7 }, 总和 = 9
5: { 2, 8 }, 总和 = 10
6: { 7, 8 }, 总和 = 15
7: { 15 }, 总和 = 15
8: { 2, 15 }, 总和 = 17
...
k = 8,所以答案 = 17(子集 {2,15})。

当然,我们可以生成每个可能的子集,整个解决方案的运行时间为 O(2^n * n),但我正在寻找更智能的东西 - 线性,或至少为 O(nk)。

最佳答案

(为简单起见,将假设非空子集。处理空子集是一两行。)

给定索引 S 的非空子集,将 Schildren 定义为 S\{max(S)} U {max(S) + 1}S U {max(S) + 1}。从 {1} 开始,子关系形成一棵树,其中包括正整数的每个非空子集。

{1}
| \
{2} {1,2}______
| \ \ \
{3} {2,3} {1,3} {1,2,3}

以相应数组元素的总和为键,这棵树是一个最小堆。如果您仔细计算 key (通过加减法而不是从头开始求和)并延迟执行最小堆删除,那么您会得到一个 O(k log k) 时间算法。

关于algorithm - 找到每个可能子集的第 k 个最小总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33219712/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com