1681. 最小不兼容性

Hard

题目描述

给你一个整数数组 nums 和一个整数 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
解释: 不可能将 nums 分配到 3 个子集中，使得同一子集中没有两个元素相等。

约束：

1 <= k <= nums.length <= 16
nums.length 能被 k 整除
1 <= nums[i] <= nums.length

解题思路

这道题需要将数组分成 k 个相等大小的子集，每个子集内元素不能重复，目标是最小化所有子集的不兼容性之和。

核心思路：

预处理判断可行性：首先统计每个数字出现的频次，如果某个数字出现超过 k 次，则无法分配到 k 个不同的子集中，直接返回 -1。
状态压缩 + 动态规划：由于数组长度最多 16，可以用位掩码表示选择的元素集合。设 dp[mask] 表示已分配元素集合为 mask 时的最小不兼容性之和。
子集枚举优化：对于每个状态，需要枚举所有可能的有效子集。一个有效子集必须满足：
- 大小等于 n/k（每个子集的大小）
- 所有元素互不相同
- 是当前未分配元素的子集
预计算有效子集：为了避免重复计算，可以预先计算所有可能的有效子集及其不兼容性值。

算法步骤：

检查可行性：统计频次，确保每个数字出现次数不超过 k
预计算所有大小为 subsetSize 且元素不重复的子集的不兼容性
使用动态规划：dp[mask] 表示分配完 mask 对应元素的最小代价
状态转移：对于每个状态，尝试添加一个有效子集

时间复杂度主要来自于枚举所有可能的子集组合，通过状态压缩和预计算优化。

代码实现

class Solution {
public:
    int minimumIncompatibility(vector<int>& nums, int k) {
        int n = nums.size();
        int subsetSize = n / k;
        
        // Check feasibility
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
            if (freq[num] > k) return -1;
        }
        
        // Precompute incompatibility for all valid subsets
        unordered_map<int, int> incomp;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != subsetSize) continue;
            
            vector<int> subset;
            unordered_set<int> seen;
            bool valid = true;
            
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    if (seen.count(nums[i])) {
                        valid = false;
                        break;
                    }
                    seen.insert(nums[i]);
                    subset.push_back(nums[i]);
                }
            }
            
            if (valid) {
                sort(subset.begin(), subset.end());
                incomp[mask] = subset.back() - subset[0];
            }
        }
        
        // DP
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            
            for (auto& [submask, cost] : incomp) {
                if ((mask & submask) == 0) { // No overlap
                    int newMask = mask | submask;
                    dp[newMask] = min(dp[newMask], dp[mask] + cost);
                }
            }
        }
        
        return dp[(1 << n) - 1] == INT_MAX ? -1 : dp[(1 << n) - 1];
    }
};

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        n = len(nums)
        subset_size = n // k
        
        # Check feasibility
        freq = Counter(nums)
        if any(count > k for count in freq.values()):
            return -1
        
        # Precompute incompatibility for all valid subsets
        incomp = {}
        for mask in range(1 << n):
            if bin(mask).count('1') != subset_size:
                continue
                
            subset = []
            seen = set()
            valid = True
            
            for i in range(n):
                if mask & (1 << i):
                    if nums[i] in seen:
                        valid = False
                        break
                    seen.add(nums[i])
                    subset.append(nums[i])
            
            if valid:
                subset.sort()
                incomp[mask] = subset[-1] - subset[0]
        
        # DP
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
                
            for submask, cost in incomp.items():
                if mask & submask == 0:  # No overlap
                    new_mask = mask | submask
                    dp[new_mask] = min(dp[new_mask], dp[mask] + cost)
        
        return dp[(1 << n) - 1] if dp[(1 << n) - 1] != float('inf') else -1

public class Solution {
    public int MinimumIncompatibility(int[] nums, int k) {
        int n = nums.Length;
        int subsetSize = n / k;
        
        // Check feasibility
        var freq = new Dictionary<int, int>();
        foreach (int num in nums) {
            freq[num] = freq.GetValueOrDefault(num, 0) + 1;
            if (freq[num] > k) return -1;
        }
        
        // Precompute incompatibility for all valid subsets
        var incomp = new Dictionary<int, int>();
        for (int mask = 0; mask < (1 << n); mask++) {
            if (CountBits(mask) != subsetSize) continue;
            
            var subset = new List<int>();
            var seen = new HashSet<int>();
            bool valid = true;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    if (seen.Contains(nums[i])) {
                        valid = false;
                        break;
                    }
                    seen.Add(nums[i]);
                    subset.Add(nums[i]);
                }
            }
            
            if (valid) {
                subset.Sort();
                incomp[mask] = subset[subset.Count - 1] - subset[0];
            }
        }
        
        // DP
        var dp = new int[1 << n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == int.MaxValue) continue;
            
            foreach (var pair in incomp) {
                int submask = pair.Key;
                int cost = pair.Value;
                
                if ((mask & submask) == 0) { // No overlap
                    int newMask = mask | submask;
                    if (dp[mask] != int.MaxValue) {
                        dp[newMask] = Math.Min(dp[newMask], dp[mask] + cost);
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1] == int.MaxValue ? -1 : dp[(1 << n) - 1];
    }
    
    private int CountBits(int mask) {
        int count = 0;
        while (mask > 0) {
            count += mask & 1;
            mask >>= 1;
        }
        return count;
    }
}

var minimumIncompatibility = function(nums, k) {
    const n = nums.length;
    const subsetSize = n / k;
    
    // Check feasibility
    const freq = new Map();
    for (const num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
        if (freq.get(num) > k) return -1;
    }
    
    // Precompute incompatibility for all valid subsets
    const incomp = new Map();
    for (let mask = 0; mask < (1 << n); mask++) {
        if (countBits(mask) !== subsetSize) continue;
        
        const subset = [];
        const seen = new Set();
        let valid = true;
        
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                if (seen.has(nums[i])) {
                    valid = false;
                    break;
                }
                seen.add(nums[i]);
                subset.push(nums[i]);
            }
        }
        
        if (valid) {
            subset.sort((a, b) => a - b);
            incomp.set(mask, subset[subset.length - 1] - subset[0]);
        }
    }
    
    // DP
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(3^n)	预计算所有子集需要 O(2^n × n)，DP 过程中每个状态需要枚举所有子集，总体为 O(3^n)
空间复杂度	O(2^n)	需要存储 DP 数组和预计算的子集不兼容性，均为 O(2^n)

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析