在 Python 中构建具有给定大小、总和和元素上限的不同元素数组

pythonserver side programmingprogramming更新于 2025/10/17 11:24:17

假设我们有一个大小变量 N，还有一个变量 SUM(这是数组中所有可用元素的总和)，以及另一个变量 K(数组中没有大于 K 的元素)，我们必须找到一个正交数组，其中数组中的所有元素都是不同的。如果没有解决方案，则返回 -1。

因此，如果输入为 N = 4、SUM = 16 K = 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 填充
sum := minimum_sum
i := N
当 i >= 1 时，执行
- x := sum + (K - i)
- 如果 x < SUM，则
  - sum := sum +(K - i)
  - res[i] := K
  - K := K - 1
- 否则，
  - res[i] := res[i] +(SUM - sum)
  - sum := SUM
  - 退出循环
- i := i - 1
返回 res

示例

让我们看看下面的实现以便更好地理解 −

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))