Hard

题目描述

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

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

如果能够满足上述条件，则返回 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 <= 10^5
  • 1 <= nums[i] <= 1000
  • m == quantity.length
  • 1 <= m <= 10
  • 1 <= quantity[i] <= 10^5
  • nums 中至多有 50 个不同的值。

解题思路

这是一个分配问题，需要用到动态规划和状态压缩技术。

核心思路：

  1. 预处理频次： 首先统计每个数字在 nums 中的出现次数，因为每个顾客需要的数字必须相同。

  2. 状态压缩DP： 由于顾客数量最多为10，可以用位掩码表示顾客的满足状态。状态 dp[mask] 表示满足 mask 中对应顾客的最小数字种类数。

  3. 预计算子集和： 对于每个顾客子集，预计算其总需求量，便于后续判断。

  4. DP转移： 对于每种数字频次，枚举所有可能的顾客子集，如果当前数字的频次能满足这个子集的总需求，则可以进行状态转移。

算法步骤：

  • 统计数字频次，降序排序以便优先尝试频次高的数字
  • 预计算所有顾客子集的需求总和
  • 使用状态压缩DP，dp[mask] 表示是否能满足 mask 对应的顾客集合
  • 对每个数字频次，枚举能满足的顾客子集进行状态转移

代码实现

class Solution {
public:
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> cnt;
        for (int num : nums) {
            cnt[num]++;
        }
        
        vector<int> freq;
        for (auto& [num, c] : cnt) {
            freq.push_back(c);
        }
        sort(freq.rbegin(), freq.rend());
        
        int m = quantity.size();
        vector<int> sum(1 << m);
        for (int mask = 1; mask < (1 << m); mask++) {
            for (int i = 0; i < m; i++) {
                if (mask & (1 << i)) {
                    sum[mask] = sum[mask ^ (1 << i)] + quantity[i];
                    break;
                }
            }
        }
        
        vector<bool> dp(1 << m);
        dp[0] = true;
        
        for (int f : freq) {
            for (int mask = (1 << m) - 1; mask >= 0; mask--) {
                if (!dp[mask]) continue;
                for (int sub = mask ^ ((1 << m) - 1); sub > 0; sub = (sub - 1) & (mask ^ ((1 << m) - 1))) {
                    if (sum[sub] <= f) {
                        dp[mask | sub] = true;
                    }
                }
            }
        }
        
        return dp[(1 << m) - 1];
    }
};

class Solution:
    def canDistribute(self, nums: List[int], quantity: List[int]) -> bool:
        from collections import Counter
        
        cnt = Counter(nums)
        freq = sorted(cnt.values(), reverse=True)
        
        m = len(quantity)
        sum_mask = [0] * (1 << m)
        
        for mask in range(1, 1 << m):
            for i in range(m):
                if mask & (1 << i):
                    sum_mask[mask] = sum_mask[mask ^ (1 << i)] + quantity[i]
                    break
        
        dp = [False] * (1 << m)
        dp[0] = True
        
        for f in freq:
            for mask in range((1 << m) - 1, -1, -1):
                if not dp[mask]:
                    continue
                complement = mask ^ ((1 << m) - 1)
                sub = complement
                while sub > 0:
                    if sum_mask[sub] <= f:
                        dp[mask | sub] = True
                    sub = (sub - 1) & complement
        
        return dp[(1 << m) - 1]

public class Solution {
    public bool CanDistribute(int[] nums, int[] quantity) {
        var cnt = new Dictionary<int, int>();
        foreach (int num in nums) {
            cnt[num] = cnt.GetValueOrDefault(num, 0) + 1;
        }
        
        var freq = cnt.Values.ToList();
        freq.Sort((a, b) => b.CompareTo(a));
        
        int m = quantity.Length;
        var sum = new int[1 << m];
        
        for (int mask = 1; mask < (1 << m); mask++) {
            for (int i = 0; i < m; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum[mask] = sum[mask ^ (1 << i)] + quantity[i];
                    break;
                }
            }
        }
        
        var dp = new bool[1 << m];
        dp[0] = true;
        
        foreach (int f in freq) {
            for (int mask = (1 << m) - 1; mask >= 0; mask--) {
                if (!dp[mask]) continue;
                int complement = mask ^ ((1 << m) - 1);
                for (int sub = complement; sub > 0; sub = (sub - 1) & complement) {
                    if (sum[sub] <= f) {
                        dp[mask | sub] = true;
                    }
                }
            }
        }
        
        return dp[(1 << m) - 1];
    }
}

var canDistribute = function(nums, quantity) {
    const cnt = new Map();
    for (const num of nums) {
        cnt.set(num, (cnt.get(num) || 0) + 1);
    }
    
    const freq = Array.from(cnt.values()).sort((a, b) => b - a);
    
    const m = quantity.length;
    const sum = new Array(1 << m).fill(0);
    
    for (let mask = 1; mask < (1 << m); mask++) {
        for (let i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                sum[mask] = sum[mask ^ (1 << i)] + quantity[i];
                break;
            }
        }
    }
    
    const dp = new Array(1 << m).fill(false);
    dp[0] = true;
    
    for (const f of freq) {
        for (let mask = (1 << m) - 1; mask >= 0; mask--) {
            if (!dp[mask]) continue;
            const complement = mask ^ ((1 << m) - 1);
            for (let sub = complement; sub > 0; sub = (sub - 1) & complement) {
                if (sum[sub] <= f) {
                    dp[mask | sub] = true;
                }
            }
        }
    }
    
    return dp[(1 << m) - 1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(U × 3^m)
空间复杂度O(2^m)

其中 U 是不同数字的个数（最多50），m 是顾客数量（最多10）。时间复杂度中的 3^m 来自于对每个数字枚举所有可能的顾客子集。