在Python中构造具有给定大小,总和和元素上限的独特元素数组
假设我们有一个大小变量N,我们还有一个变量SUM,它是数组中所有可用元素的总和,而另一个变量K,使得数组中没有元素大于K,我们必须找到一个正交数组数组中所有元素都不同的地方。如果没有解决方案,则返回-1。
因此,如果输入类似于N=4,SUM=16K=9,则输出将为[1,2,4,9]
为了解决这个问题,我们将遵循以下步骤-
minimum_sum:=(N*(N+1))/2
maximum_sum:=(N*K)-(N*(N-1))/2
如果minimum_sum>SUM或maximum_sum<SUM,则
返回-1
res:=一个大小为N+1的数组,并用0到N填充
总和:=minimum_sum
i:=N
当我>=1,
res[i]:=res[i]+(SUM-总和)
总和:=SUM
从循环中出来
和:=和+(K-i)
res[i]:=K
K:=K-1
x:=和+(K-i)
如果x<SUM,则
除此以外,
我:=我-1
返回资源
示例
让我们看下面的实现以更好地理解-
def get_arr(N, SUM, K): minimum_sum = (N * (N + 1)) / 2 maximum_sum = (N * K) - (N * (N - 1)) / 2 if (minimum_sum > SUM or maximum_sum < SUM): return -1 res = [i for i in range(N + 1)] sum = minimum_sum i = N while(i >= 1): x = sum + (K - i) if (x < SUM): sum = sum + (K - i) res[i] = K K -= 1 else: res[i] += (SUM - sum) sum = SUM break i -= 1 return res N = 4 SUM = 16 K = 9 print(get_arr(N, SUM, K))
输入值
4, 16, 9
输出结果
[0, 1, 2, 4.0, 9]