题目描述
给你一个整数数组nums
和一个整数k
。你需要将这个数组划分到k
个相同大小的子集中,使得同一个子集里面没有两个相同的元素。
一个子集的 不兼容性 是该子集里面最大值和最小值的差。
请你返回将数组分成 k
个子集后,各子集 不兼容性 的 和
的 最小值
,如果无法分成分成 k
个子集,返回-1
。
子集的定义是数组中一些数字的集合,对数字顺序没有要求。
样例
示例1
输入:nums = [1,2,1,4], k = 2
输出:4
解释:最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和,但是第一个集合有 2 个相同的元素,所以不可行。
示例2
输入:nums = [6,3,8,1,3,1,2,2], k = 4
输出:6
解释:最优的子集分配为 [1,2],[2,3],[6,8] 和 [1,3] 。
不兼容性和为 (2-1) + (3-2) + (8-6) + (3-1) = 6 。
示例3
输入:nums = [5,3,3,6,3,3], k = 3
输出:-1
解释:没办法将这些数字分配到 3 个子集且满足每个子集里没有相同数字。
提示
1 <= k <= nums.length <= 16
nums.length 能被 k 整除
1 <= nums[i] <= nums.length
算法1
(状态压缩 + 剪枝 动态规划) $O(n2^n)$
- 定义所有合法的单个最小集合
st
以及总集合的划分方式f
,状态数量分别为t
和t2
,f[i]
表示用了用了二进制状态下i
的位为1
的数. - 利用二进制枚举子集,统计出
st
和f
- 每一个集合的元素个数应该为
cnt = n / k
- 合法的单个集合
__builtin_popcount(i) == cnt
- 合法的整体总集合
__builtin_popcount(i) %cnt == 0
- 合法的单个集合中,不可以有相同数字。
- 每一个集合的元素个数应该为
- 因此对于单个集合的合法性我封装成了一个函数
check
,在计算合法的同时返回集合的不兼容性,如果返回-1表示集合不合法 - 初始化
f[i]
为INF
, 但对于i==st[k]
的状态(最小单个集合),初始化成st[k]
的不兼容性 - 枚举所有
f
的状态state
, 再枚举所有可行的单个集合ss
,ss
属于st
, 如果ss
是state
的一个子集, 那么尝试更新f[state]
的值。 - 由于
state
的状态是从小到大的,那么当ss >= state
时就可以停止枚举子集. 判断一个二进制状态是否是另一个数的二进制状态可以通过state | ss == state
来判断,因为当state
与ss
有一位不同时,等式将不成立 - 最终答案即为
f[(1 << n) - 1]
时间复杂度
- 为了方便统计,一些非常小的复杂度,例如
check
函数, 对nums
排序不做赘述 - 枚举所有单个最小集合和总集合需要枚举状态
1 << n
次,复杂度为$O(2^n)$ - 每一个状态的
check
需要的时间为$(O(n))$ (n <= 16, 固定计算16次) - 合法的最小子集数量是一个组合数,值为$T1 = C_{n}^{n/k} * C_{n - n / k}^{n/k}… $
- 合法的大集合数量也是一个组合数,值为$T2 = C_{n}^{n/k} + C_{n}^{n/k * 2} + C_{n}^{n/k * 3} + … $
- 总时间复杂度为 $T1 * T2 + n2^n$.
- 公式化简太麻烦了。。但是由于子集数量有限,一般考虑$O(T1 * T2) <= 2^n$,故总时间复杂度为$O(n2^n)$
C++ 代码
pair<int, int> st[1 << 16]; // first 表示状态, second表示不兼容性
int alls[1 << 16];
int f[1 << 16];
#define INF 0x3f3f3f3f
class Solution {
public:
int check(vector<int> & nums, int x){
int p[16] = {}, idx = 0;
for(int i = 0; i < 16; i++){
if(x >> i & 1) p[idx++] = i;
}
for(int i = 0; i < idx - 1; i++){
if(nums[p[i]] == nums[p[i + 1]]) return -1;
}
return nums[p[idx - 1]] - nums[p[0]];
}
int minimumIncompatibility(vector<int>& nums, int k) {
memset(f, 0x3f, sizeof f);
int n = nums.size();
sort(nums.begin(), nums.end());
int cnt = n / k, t = 0, t2 = 0;
for(int i = 1; i < 1 << n; i++){
int cnt1 = __builtin_popcount(i);
if(cnt1 % cnt == 0) alls[t2++] = i;
if(cnt1 == cnt){
int diff = check(nums, i);
if(diff != -1) {
st[t++] = {i, diff};
f[i] = diff;
}
}
}
for(int i = 0; i < t2; i++){
int state = alls[i];
for(int j = 0; j < t && st[j].first < state; j++){
int ss = st[j].first;
if((state | ss) == state){
f[state] = min(f[state], f[state - ss] + st[j].second);
}
}
}
int ans = f[(1 << n) - 1];
return ans == INF ? -1 : ans;
}
};
tql
除夕哥教得好啊
抓住0.0