在Python中找到从n个球中随机选择k个球的最大和最小元素之间的差异和的程序

在Python中找到从n个球中随机选择k个球的最大和最小元素之间的差异和的程序

假设我们有由数组nums编号的n个球,其大小为n,nums [i]表示球i的数量。现在有另一个值k. 每次我们从n个不同的球中选择k个球,并找到k个球的最大和最小值的差异,并将差异存储在表格中。然后将这些k个球再次放入那个锅中并再次选择,直到我们选择了所有可能的选择。最后从表中找到所有差异的总和。如果答案太大,则返回结果mod 10 ^ 9 + 7。

所以,如果输入如n = 4 k = 3 nums = [5, 7, 9, 11],则输出将为20,因为组合为 –

  • [5,7,9],差为9-5= 4
  • [5,7,11],差为11-5 = 6
  • [5,9,11],差为11-5 = 6
  • [7,9,11],差为11-7 = 4

,因此4 + 6 + 6 + 4 = 20。

为了解决这个问题,我们将遵循以下步骤 –

  • m:= 10 ^ 9 + 7
  • inv:具有元素[0,1]的新列表
  • 对于i在范围2到n中,执行
    • 将(m-地板(m / i)* inv [m mod i] mod m)插入inv的末尾
  • comb_count:= 1
  • res:= 0
  • 对于选择范围k-1至n-1,执行
    • res:= res +(nums [pick] – nums [n-1-pick])* comb_count mod m
    • res:= res mod m
    • comb_count:= comb_count *(pick + 1)mod m * inv [pick + 2-k] mod m
  • 返回res

示例

让我们看以下实现以获得更好的理解–

def solve(n, k, nums):
   m = 10**9 + 7
   inv = [0, 1]
   for i in range(2, n + 1):
      inv.append(m - m // i * inv[m % i] % m)

   comb_count = 1
   res = 0
   for pick in range(k - 1, n):
      res += (nums[pick] - nums[n - 1 - pick]) * comb_count % m
      res %= m
      comb_count = comb_count * (pick + 1) % m * inv[pick + 2 - k] % m

   return res

n = 4
k = 3
nums = [5, 7, 9, 11]
print(solve(n, k, nums))

输入

4, 3, [5, 7, 9, 11]

输出

20

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程