Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

你的任务是确定是否可以将 nums 的所有元素分割成一个或多个组，使得：

  • 每个组恰好包含 k 个元素。
  • 每个组中的所有元素都是不同的。
  • nums 中的每个元素必须恰好分配给一个组。

如果这样的分割是可能的，返回 true，否则返回 false。

示例 1：

输入：nums = [1,2,3,4], k = 2
输出：true
解释：
一种可能的分割是有 2 个组：
- 组 1：[1, 2]
- 组 2：[3, 4]
每个组包含 k = 2 个不同的元素，所有元素恰好使用一次。

示例 2：

输入：nums = [3,5,2,2], k = 2
输出：true
解释：
一种可能的分割是有 2 个组：
- 组 1：[2, 3]
- 组 2：[2, 5]
每个组包含 k = 2 个不同的元素，所有元素恰好使用一次。

示例 3：

输入：nums = [1,5,2,3], k = 3
输出：false
解释：
我们无法使用所有值恰好一次形成 k = 3 个不同元素的组。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • 1 <= k <= nums.length

解题思路

这道题的核心思路是通过数学分析来判断分割的可行性。

首先分析分割的基本条件：

  1. 总元素数量必须能被 k 整除，这样才能形成完整的组
  2. 每个组需要 k 个不同的元素，所以如果某个元素出现次数过多，就无法满足要求

具体分析过程：

  • 如果数组长度 n 不能被 k 整除，直接返回 false
  • 计算需要形成的组数：groups = n / k
  • 统计每个元素的出现频次
  • 关键观察：由于每个组只能包含一个相同的元素，任何元素的出现次数都不能超过组数 groups

举例说明：如果 nums = [2,2,2,1,3,4], k = 2，那么 groups = 6/2 = 3。元素 2 出现了 3 次，恰好等于组数，可以在每组中放一个 2。如果元素 2 出现 4 次，由于只有 3 个组，就无法分配。

这种方法的优势是不需要实际构造分组，只需要验证数学条件即可，时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    bool partitionArray(vector<int>& nums, int k) {
        int n = nums.size();
        if (n % k != 0) return false;
        
        int groups = n / k;
        unordered_map<int, int> freq;
        
        for (int num : nums) {
            freq[num]++;
            if (freq[num] > groups) return false;
        }
        
        return true;
    }
};

class Solution:
    def partitionArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        if n % k != 0:
            return False
        
        groups = n // k
        freq = {}
        
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
            if freq[num] > groups:
                return False
        
        return True

public class Solution {
    public bool PartitionArray(int[] nums, int k) {
        int n = nums.Length;
        if (n % k != 0) return false;
        
        int groups = n / k;
        Dictionary<int, int> freq = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
            
            if (freq[num] > groups) return false;
        }
        
        return true;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var partitionArray = function(nums, k) {
    const n = nums.length;
    if (n % k !== 0) return false;
    
    const groups = Math.floor(n / k);
    const freq = new Map();
    
    for (const num of nums) {
        const count = (freq.get(num) || 0) + 1;
        freq.set(num, count);
        
        if (count > groups) return false;
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是数组的长度。时间复杂度为 O(n) 因为需要遍历数组一次统计频次；空间复杂度为 O(n) 因为在最坏情况下（所有元素都不同）需要存储 n 个不同元素的频次。