分配重复整数

标签: 位运算 数组 动态规划 回溯 状态压缩

难度: Hard

给你一个长度为 n 的整数数组 nums ，这个数组中至多有 50 个不同的值。同时你有 m 个顾客的订单 quantity ，其中，整数 quantity[i] 是第 i 位顾客订单的数目。请你判断是否能将 nums 中的整数分配给这些顾客，且满足：

  • 第 i 位顾客 恰好 有 quantity[i] 个整数。
  • 第 i 位顾客拿到的整数都是 相同的 。
  • 每位顾客都满足上述两个要求。

如果你可以分配 nums 中的整数满足上面的要求，那么请返回 true ，否则返回 false 。

示例 1：

输入：nums = [1,2,3,4], quantity = [2]
输出：false
解释：第 0 位顾客没办法得到两个相同的整数。

示例 2：

输入：nums = [1,2,3,3], quantity = [2]
输出：true
解释：第 0 位顾客得到 [3,3] 。整数 [1,2] 都没有被使用。

示例 3：

输入：nums = [1,1,2,2], quantity = [2,2]
输出：true
解释：第 0 位顾客得到 [1,1] ，第 1 位顾客得到 [2,2] 。

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= 1000
  • m == quantity.length
  • 1 <= m <= 10
  • 1 <= quantity[i] <= 105
  • nums 中至多有 50 个不同的数字。

Submission

运行时间: 71 ms

内存: 24.7 MB

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        Cnt=Counter(nums)
        cnt=[]
        for i in Cnt:
            cnt.append(Cnt[i])
        cnt.sort(reverse=True)
        quantity.sort(reverse=True)
        n,m=len(nums),len(quantity)
        N=len(cnt)
        #将集合划分成m个子集，子集内的元素都是相同的,子集的大小时quantity[i]

        #将集合划分成k个子集,子集内的元素和都是相同的,子集的大小是k
        
        
        def dfs(i): # i是哪个顾客 
            if i==m:
                return True
            Map=set()
            for j in range(N):
                if cnt[j] in Map: #前面出现过相似的情况,不能成功，那我现在也不重复了
                    continue
                if cnt[j]>=quantity[i]:
                    cnt[j]-=quantity[i] 
                    if dfs(i+1):
                        return True
                    cnt[j]+=quantity[i]
                    Map.add(cnt[j])
            return False          
        
        return dfs(0)

Explain

这个题解采用了回溯的方法。首先，统计nums中每个数字出现的次数，并按照出现次数降序排序。然后，也将顾客订单的数量按照降序排序。接着，使用深度优先搜索（DFS）尝试为每个顾客分配订单。对于每个顾客，遍历统计的数字出现次数列表，尝试从中分配足够的数量给顾客。如果当前数字剩余的数量足够，并且之前没有尝试过这个数量（通过一个集合Map来记录），则进行尝试，并递归地处理下一个顾客。如果所有顾客都能成功分配，则返回true，否则回溯并尝试其他分配方案。

时间复杂度: O(N^m)

空间复杂度: O(m + N)

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        Cnt=Counter(nums)
        cnt=[]
        for i in Cnt:
            cnt.append(Cnt[i])
        cnt.sort(reverse=True)
        quantity.sort(reverse=True)
        n,m=len(nums),len(quantity)
        N=len(cnt)
        
        def dfs(i): # i是哪个顾客 
            if i==m:
                return True
            Map=set()
            for j in range(N):
                if cnt[j] in Map: #前面出现过相似的情况,不能成功，那我现在也不重复了
                    continue
                if cnt[j]>=quantity[i]:
                    cnt[j]-=quantity[i] 
                    if dfs(i+1):
                        return True
                    cnt[j]+=quantity[i]
                    Map.add(cnt[j])
            return False          
        
        return dfs(0)

Explore

回溯是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被证明不是一个有效的解，回溯算法会丢弃它，并回退到之前的步骤，尝试其他可能的解。在这个问题中，回溯用于尝试为每个顾客分配他们需要的数量。从第一个顾客开始，尝试给他分配足够的数量，如果能成功，递归地尝试为下一个顾客分配。如果某一步分配失败，算法则取消上一步的分配（即回溯），尝试其他可能的分配方式。这样，算法可以找到是否存在一种分配方式能满足所有顾客的需求。

将数字出现的次数和顾客订单数量进行降序排序的目的是为了尽可能快地减少搜索空间。通过优先考虑需要更多数量的顾客和拥有更多库存的数字，算法首先尝试满足最难满足的订单，这样在早期阶段可能就能确定某些分配是不可能的，从而提前终止无效的搜索路径，加快算法的效率。

在尝试分配给顾客之后，如果失败，需要进行回溯是因为当前尝试的分配方案不能满足后续顾客的需求，我们需要撤销当前的分配，并尝试其他可能的分配方案。具体的回溯操作是通过在递归函数中，当一个分配尝试失败（即dfs返回False）后，恢复之前修改的状态（即将先前分配给顾客的数量加回到对应数字的剩余数量中），然后继续尝试下一个可能的分配。这样可以确保每一次递归调用都在探索一个新的分配可能性。

集合`Map`用于记录在尝试分配过程中已经尝试过的数字的数量，以避免重复尝试相同的失败分配方案。当尝试为一个顾客分配某个数量而失败后，该数量会被加入到`Map`中。如果后续再次考虑到相同的数量，算法会直接跳过，避免无意义的重复计算。这样可以减少算法的时间复杂度，提高效率。