区分n个数,使得和等于N.

Question

假设我想在1到N的范围内找到n个不同的数字,因此它们的和等于N.例如

n = 3, N = 10: the numbers will be (2, 3, 5);
n = 4, N = 10: the numbers will be (1, 2, 3, 4).

虽然找出这个问题的所有可能组合将需要指数时间,但我正在寻找"最小"组合,即最大数字是最小的.例如,

在这种情况下n = 4, and N = 12,两者都(6, 3, 2, 1) and (5, 4, 2, 1)可以解决,但我只对此感兴趣(5, 4, 2, 1).

对于这个问题,是否会有一个具有更好时间复杂度的算法？我听说过对数合并,但不知道如何在这里应用.

如果需要指明问题的任何细节,请告诉我.总是,任何帮助将非常感激.

Answer 1

这个问题有一个简单的贪婪算法.

首先,有n个元素按升序排列,为了使它们不同,每个元素应该比其前一个元素大至少一个.

所以,我们有

1, 2, 3 ... , n

现在,所有n数字的总和是n*(n + 1)/2

剩下的是 left = N - n*(n + 1)/2

为了使最后一个元素尽可能小,我们需要将left差异分散到所有数字

所以,我们有

1 + left/n, 2 + left/n, ..., n + left/n

如果left % n != 0,我们只需要在最后一个left % n元素中添加额外的1 .

注意:如果N < n*(n + 1)/2,没有解决方案

例:

因此,对于n = 4和N = 12

First, we start with

1, 2, 3, 4

left = 12 - (4*5/2) = 2

So, now we have

1 + (2/4), 2 + (2/4), 3 + (2/4), 4 + (2/4) = 1, 2, 3, 4

As left % n = 2
Finally, we have

1, 2, 3 + 1, 4 + 1 = 1, 2, 4, 5

类似地,对于n = 3,N = 10

First, we start with

1, 2, 3

left = 10 - (3*4/2) = 4

So, now we have

1 + (4/3), 2 + (4/3), 3 + (4/3) = 2, 3, 4

As left % n = 1
Finally, we have

2, 3, 4 + 1 = 2, 3, 5

伪码,时间复杂度O(n)

int[]result = new int[n];
int left = N - n*(n + 1)/2;

for(int i = 0; i < n; i++){
    result[i] = i + 1 + left/n;
    if(i >= n - (left % n)){//Add extra one for last left % n elements
        result[i]++;
    }
}
return result;