原文链接: https://leetcode-cn.com/problems/distribute-repeating-integers

英文原文

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the ith customer ordered. Determine if it is possible to distribute nums such that:

• The ith customer gets exactly quantity[i] integers,
• The integers the ith customer gets are all equal, and
• Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

 

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

 

Constraints:

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= 1000
• m == quantity.length
• 1 <= m <= 10
• 1 <= quantity[i] <= 105
• There are at most 50 unique values in nums.

中文题目

给你一个长度为 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] 。

示例 4：

输入：nums = [1,1,2,3], quantity = [2,2]
输出：false
解释：尽管第 0 位顾客可以得到 [1,1] ，第 1 位顾客没法得到 2 个一样的整数。

示例 5：

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

 

提示：

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

通过代码

高赞题解

状态压缩

首先，容易发现 $\textit{nums}$ 的具体取值是不重要的：只有每个取值出现的次数是重要的。因此，我们构造 $\textit{nums}$ 的频次数组 $\textit{cnt}$，代表了原数组中每个数字出现的次数。

例如，在数组 $[3,2,2,5]$ 中，只有数字 $2$ 出现了 $2$ 次，故频次数组为 $[1,2,1]$（其顺序无关紧要）。

考虑到订单数目最多为 $10$，故使用状态压缩动态规划解决本题：用一个 $0 - 2^{10}(=1024)$ 的整数代表 $m$ 个顾客的一个子集。随后，用 $dp[i][j]$ 表示：$\textit{cnt}$ 数组中的前 $i$ 个元素，能否满足顾客的子集合 $j$ 的订单需求。

考虑 $dp[i][j]$ 时，为了满足子集 $j$ 的需求，我们可以让 $\textit{cnt}[i]$ 满足 $j$ 的某个子集 $s$， 并让 $\textit{cnt}[0..i-1]$ 满足子集 $j-s$。对于特定的某个子集 $s$ 而言，该种方案如果可行，必然有 $dp[i-1][j-s]$ 为 $true$，且子集 $s$ 的订单需求总和不超过 $cnt[i]$。

因此，当且仅当能找到这样的子集 $s$ 时，$dp[i][j]=true$。

class Solution {
public:
    bool canDistribute(vector<int>& nums, vector<int>& quantity) {
        unordered_map<int, int> cache;
        for (int x: nums) {
            cache[x]++;
        }
        vector<int> cnt;
        for (auto& kv: cache) {
            cnt.push_back(kv.second);
        }
        
        int n = cnt.size(), m = quantity.size();
        vector<int> sum(1 << m, 0);
        for (int i = 1; i < (1 << m); i++) {
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) != 0) {
                    int left = i - (1 << j);
                    sum[i] = sum[left] + quantity[j];
                    break;
                }
            }
        }
        
        vector<vector<bool>> dp(n, vector<bool>(1 << m, false));
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < (1 << m); j++) {
                if (i > 0 && dp[i-1][j]) {
                    dp[i][j] = true;
                    continue;
                }
                for (int s = j; s != 0; s = ((s - 1) & j)) { // 子集枚举，详见 https://oi-wiki.org/math/bit/#_14
                    int prev = j - s; // 前 i-1 个元素需要满足子集 prev = j-s
                    bool last = (i == 0) ? (prev == 0): dp[i-1][prev]; // cnt[0..i-1] 能否满足子集 prev
                    bool need = sum[s] <= cnt[i]; // cnt[i] 能否满足子集 s
                    if (last && need) {
                        dp[i][j] = true;
                        break;
                    }
                }
            }
        }
        return dp[n-1][(1<<m)-1];
    }
};

复杂度分析

• 时间复杂度：$O(n\cdot 3^m)$，其中 $n$ 为 $\textit{nums}$ 中不同整数的数量，$m$ 为 $\textit{quantity}$ 的大小。
• 空间复杂度：$O(n \cdot 2^m)$。

统计信息

通过次数	提交次数	AC比率
2214	5801	38.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言