列表

详情

1681. 最小不兼容性

给你一个整数数组 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 个子集且满足每个子集里没有相同数字。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minimumIncompatibility(vector<int>& nums, int k) { } };

javascript 解法, 执行用时: 592 ms, 内存消耗: 50.7 MB, 提交时间: 2023-06-28 09:37:16 

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumIncompatibility = function(nums, k) {
    const n = nums.length, group = n / k, inf = Infinity;
    const dp = new Array(1 << n).fill(inf);
    dp[0] = 0;
    const values = new Map();

    for (let mask = 1; mask < (1 << n); mask++) {
        if (countOnes(mask) !== group) {
            continue;
        }
        let mn = 20,
            mx = 0;
        const cur = new Set();
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) > 0) {
                if (cur.has(nums[i])) {
                    break;
                }
                cur.add(nums[i]);
                mn = Math.min(mn, nums[i]);
                mx = Math.max(mx, nums[i]);
            }
        }
        if (cur.size == group) {
            values.set(mask, mx - mn);
        }
    }

    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == inf) {
            continue;
        }
        const seen = new Map();
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                seen.set(nums[i], i);
            }
        }
        if (seen.size < group) {
            continue;
        }
        let sub = 0;
        for (let v of seen.values()) {
            sub |= (1 << v);
        }
        let nxt = sub;
        while (nxt > 0) {
            if (values.has(nxt)) {
                dp[mask | nxt] = Math.min(dp[mask | nxt], dp[mask] + values.get(nxt));
            }
            nxt = (nxt - 1) & sub;
        }
    }

    return (dp[(1 << n) - 1] < inf) ? dp[(1 << n) - 1] : -1;
}

function countOnes(n) {
    let count = 0;
    while (n > 0) {
        count++;
        n &= n - 1;
    }
    return count;
}

java 解法, 执行用时: 21 ms, 内存消耗: 53.5 MB, 提交时间: 2023-06-28 09:36:20 

class Solution {

    int len, n;
    int[][] memo;
    int[] nums;
    int inf = (int)1e9 + 7;
    
    public int minimumIncompatibility(int[] nums, int k) {
        n = nums.length;
        len =  n / k;
        this.nums = nums;
        int[] count = new int[n + 1];
        for(int e : nums) ++count[e];
        for(int e : count) if(e > k) return -1;

        int m = 1 << n;
        memo = new int[m - 1][n];
        for(int i = 0; i < m - 1; ++i) Arrays.fill(memo[i], -1);
        Arrays.sort(nums);
        return dfs(m - 2, 0);
    }
    
    public int dfs(int left, int pre) {

        if(left == 0) return 0;
        if(memo[left][pre] > -1) return memo[left][pre];
        //创建一个新的组
        if(Integer.bitCount(left) % len == 0){

            int lowbit = left & -left;
            return dfs(left ^ lowbit, 32 - Integer.numberOfLeadingZeros(lowbit) - 1);
        }
        int res = inf;
        int last = nums[pre];
        for(int i = pre + 1; i < n; ++i) //枚举本组的下一个数
            if((left >> i & 1) > 0 && nums[i] != last){ //判断重复数字
                last = nums[i];
                res = min(res, last - nums[pre] + dfs( left ^ 1 << i, i));
            }
        return memo[left][pre] = res;
    }
    
    public int min(int a, int b){ return a < b ? a : b; }
}

golang 解法, 执行用时: 200 ms, 内存消耗: 6.4 MB, 提交时间: 2023-06-28 09:33:27 

func minimumIncompatibility(nums []int, k int) int {
	n := len(nums)
	if k == n {
		return 0
	}
	cnt := make([]int, n+1)
	for _, num := range nums {
		cnt[num]++
		if cnt[num] > k {  // 存在某个数的数量超过k个，直接返回-1
			return -1
		}
	}
	m, div := 1<<uint(n), n/k
	f, sum := make([]int, m), make([]int, m)
	for i := range sum { // 预处理可以划分为同一个子集的所有情况
		sum[i] = 1000
		if bits.OnesCount(uint(i)) == div {
			curSum, curMax, curMin := 0, 0, n
			for j := i; j > 0; j ^= j & -j {    // 参考树状数组的get  从低到高遍历i的每一个1
				jj := bits.TrailingZeros(uint(j))
				curSum |= 1 << uint(nums[jj])
				curMax, curMin = max(curMax, nums[jj]), min(curMin, nums[jj])
			}
			if bits.OnesCount(uint(curSum)) == div {
				sum[i] = curMax - curMin
			}
		}
	}
	for mask := 1; mask < m; mask++ {
		if bits.OnesCount(uint(mask))%div == 0 {  // 只有mask中的1的数量可以被div整除，mask才可以进行有效的状态转移
			f[mask] = 1000
			for sub := mask; sub > 0; sub = (sub - 1) & mask {
				f[mask] = min(f[mask], f[mask^sub]+sum[sub])
			}
		}
	}
	if f[m-1] == 1000 {
		return -1
	}
	return f[m-1]
}

func min(a int, b int) int { if a < b { return a }; return b }
func max(a int, b int) int { if a > b { return a }; return b }

python3 解法, 执行用时: 112 ms, 内存消耗: 24.3 MB, 提交时间: 2023-06-28 09:29:54 

class Solution:
    def minimumIncompatibility(self, a: List[int], k: int) -> int:
        from collections import Counter
        if any(c > k for c in Counter(a).values()):  # 鸽巢原理
            return -1

        n = len(a)
        size = n // k
        a.sort()  # 排序，便于判断重复

        @cache
        def dfs(left: int, pre: int) -> int:
            if left == 0: return 0
            if left.bit_count() % size == 0:  # 创建一个新的组
                lb = left & -left  # 选择 lowbit 作为第一个数
                return dfs(left ^ lb, lb.bit_length() - 1)
            res = inf
            last = a[pre]
            for i in range(pre + 1, n):  # 枚举这个组的下一个数
                if left >> i & 1 and a[i] != last:  # 组内不能有重复数字，且 a 中重复数字只需枚举一次
                    last = a[i]
                    res = min(res, last - a[pre] + dfs(left ^ (1 << i), i))
            return res

        return dfs((1 << n) - 2, 0)

上一题

© 2024 leetcode.cn