上次我发现有趣的问题,我被困在上面.
给定n个数a [1],...,a [n]按升序排列,数字k(1 <= n,k <= 10 ^ 5).
假设我们用sum对每个可能的给定序列子集进行排序.
我们必须找到第k个这样的子集的总和.
例如:
n = 4,k = 8
a = {2,7,8,15}
1:{2},sum = 2
2:{7},sum = 7
3:{8},sum = 8
4:{2,7},sum = 9
5:{2,8},sum = 10
6 :{7,8},sum = 15
7:{15},sum = 15
8:
{2,15} ,sum = 17
...
k = 8,所以answer = 17(子集{2,15}).
当然,我们可以生成每个可能的子集,整个解决方案在O(2 ^ n*n)中运行,但我正在寻找更智能的东西 - 线性,或至少O(nk).
我们有以下算法:
while(a > b) {
a -= c;
}
给出a,b和c,b和c是常数,c> 0.
现在它在线性时间内工作.是否有可能加快速度,以对数或恒定时间工作？