Python 中分配重复整数的程序

假设我们有一个数组 nums，最多有 50 个唯一值。我们还有一个名为 quantity 的数组，其中 quantity[i] 表示第 i 个客户订购的值的数量。我们必须检查是否可以分配 nums，使得

• 第 i 个客户恰好获得 quantity[i] 个项目，

• 第 i 个客户获得的值都相等，并且

• 所有客户都满意。

因此，如果输入类似于 nums = [5,1,2,2,3,4,4,3,3] quantity = [2,2,3]，则输出将为 True，因为两个客户各想要两个元素，因此他们可以获得 [2,2] 和 [4,4]，第三个客户想要三个项目，他们可以获得 [3,3,3]，因此所有客户都满意。

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

• 定义一个函数 util()。这将接收 i、cntr 作为参数。

• 如果 i 等于 quantity 的大小，则

  • 返回 True

• temp_counter := 创建 cntr 的副本

• 对于 cntr 中的每个 cnt，执行以下操作：

  • 如果 cnt >= quantity[i]，则

    • temp_counter[cnt] := temp_counter[cnt] - 1

    • 如果 temp_counter[cnt] 等于 0，则

      • 从 temp_counter 中删除第 cnt 个元素

    • rem := cnt - quantity[i]

    • temp_counter[rem] := temp_counter[rem] + 1

    • 如果 util(i+1, temp_counter) 为真，则

      • 返回 True

    • temp_counter[rem] := temp_counter[rem] - 1

    • 如果 temp_counter[rem] 等于 0，则

      • 从 temp_counter 中删除第 rem 个元素

  • temp_counter[cnt] := temp_counter[cnt] + 1

• 返回 False

• 从主方法中执行以下操作

• cnt := 保存 nums 中存在的数字的所有频率的频率的映射

• 按降序排列 quantity

• 返回 util(0, cnt)

示例

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

from collections import Counter
def solve(nums, quantity):
   def util(i, cntr):
      if i == len(quantity):
         return True

      temp_counter = cntr.copy()
      for cnt in cntr:
         if cnt >= quantity[i]:
            temp_counter[cnt] -= 1
            if temp_counter[cnt] == 0:
               temp_counter.pop(cnt)
         rem = cnt - quantity[i]
         temp_counter[rem] += 1

         if util(i+1, temp_counter):
            return True

         temp_counter[rem] -= 1
         if temp_counter[rem] == 0:
            temp_counter.pop(rem)
         temp_counter[cnt] += 1

      return False

   cnt = Counter(Counter(nums).values())
   quantity.sort(reverse=True)
   return util(0, cnt)

nums = [5,1,2,2,3,4,4,3,3]
quantity = [2,2,3]
print(solve(nums, quantity))

输入

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

输出

True

Arnab Chakraborty

更新于： 2021年10月7日

129 次查看

开启您的 职业生涯

通过完成课程获得认证

开始