最小不兼容性

难度: Hard

给你一个整数数组 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

Submission

运行时间: 57 ms

内存: 16.0 MB

# https://space.bilibili.com/206214
class Solution:
    def minimumIncompatibility(self, arr: List[int], k: int) -> int:
        if any(c > k for c in Counter(arr).values()):
            return -1

        n = len(arr)
        size = n // k
        arr.sort()
        ans = inf

        def dfs(left: int, pre: int, cost: int) -> int:
            if left == 0:
                nonlocal ans
                ans = cost
            else:
                if left.bit_count() % size == 0:
                    lb = left & -left
                    return dfs(left ^ lb, lb.bit_length() - 1, cost)
                last = arr[pre]
                for i in range(pre + 1, n):
                    if left >> i & 1 and arr[i] != last:
                        last = arr[i]
                        cur = cost + last - arr[pre]
                        if cur < ans:
                            dfs(left ^ (1 << i), i, cur)
                            
        dfs((1 << n) - 2, 0, 0)
        return ans

Explain

首先检查是否有任何数字出现次数超过k次，如果有，直接返回-1，因为无法形成k个不包含相同元素的子集。之后通过深度优先搜索（DFS）尝试形成所有可能的子集，并计算不兼容性的总和。使用一个整数的位表示法来跟踪哪些元素已被选择。基于位运算的技巧，例如left.bit_count()和left & -left，用来控制和优化搜索过程。如果当前已组成的子集大小达到应有的大小，则尝试开始新的子集。如果找到一个可行的分配方式，那么更新最小不兼容性。这个算法依赖于位运算和回溯来遍历所有可能的子集组合。

时间复杂度: O(2^n)

空间复杂度: O(n)

# https://space.bilibili.com/206214
class Solution:
    def minimumIncompatibility(self, arr: List[int], k: int) -> int:
        # 检查是否有元素的出现次数超过k次，如果有就无法分配
        if any(c > k for c in Counter(arr).values()):
            return -1

        n = len(arr)
        size = n // k
        arr.sort()
        ans = inf

        # 定义深度优先搜索函数
        def dfs(left: int, pre: int, cost: int) -> int:
            # 如果没有剩余元素，更新答案
            if left == 0:
                nonlocal ans
                ans = cost
            else:
                # 如果完成一个子集，开始新的子集
                if left.bit_count() % size == 0:
                    lb = left & -left
                    return dfs(left ^ lb, lb.bit_length() - 1, cost)
                last = arr[pre]
                # 遍历所有可能的下一个元素
                for i in range(pre + 1, n):
                    if left >> i & 1 and arr[i] != last:
                        last = arr[i]
                        cur = cost + last - arr[pre]
                        # 只在当前成本小于已找到的最佳解时进行递归
                        if cur < ans:
                            dfs(left ^ (1 << i), i, cur)
                            
        # 从第一个元素开始，所有元素都是可选的（除了最后一个元素，因为它必须被选中）
        dfs((1 << n) - 2, 0, 0)
        return ans

Explore

选择使用深度优先搜索(DFS)来解决这个问题主要是因为问题的本质是查找所有可能的子集组合以找到满足条件的最优分配。DFS是在组合问题中常用的方法，能够有效探索所有可能的子集配置。动态规划通常适用于有明确子问题重叠和最优子结构的问题，而本问题中子集的选择相互独立，且状态空间非常大，使用动态规划可能导致状态数过多，难以管理。此外，DFS允许回溯，这对于探索不同的组合尝试是非常有用的。

使用位运算来跟踪元素的选择状态相比传统的数组或集合具有一些明显的优势。优势包括更快的计算速度，因为位运算（如AND, OR, XOR等）在硬件级别上非常高效；空间效率高，一个整数可以表示多达32或64位的状态，这降低了内存使用。然而，位运算的劣势包括可读性较差，对于不熟悉位操作的人来说代码可能难以理解；另外，位运算的操作限制了元素数量，即只能处理位数等于整数位数的情况，对于更大的数据集需要更复杂的数据结构如位图。

在题解中提到的方法已经是一个相对高效的预处理步骤，即通过计数来直接确定是否有元素的出现次数超过k次。这种方式可以在进一步的搜索之前快速判断是否存在有效的解决方案，从而避免了不必要的计算。虽然这种方法已经很高效，但进一步的优化可能包括并行处理元素计数或使用更高效的数据结构来加速查找和更新操作。然而，对于大多数实际应用场景，使用简单的计数器就足够了，因为这步预处理的计算复杂度仅为O(n)，并且在空间复杂度上也非常高效。