力扣100097. 合法分组的最少组数（哈希+贪心）

题目描述：

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。

如果以下条件成立，我们说这个分组方案是合法的：

• 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
• 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。

请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

示例 1：

输入：nums = [3,2,3,2,3]

输出：2

解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：

组 1 -> [0,2,4]

组 2 -> [1,3]

所有下标都只属于一个组。

组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。

组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。

组 1 中下标数目为 3 ，组 2 中下标数目为 2 。

两者之差不超过 1 。

无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。

所以答案为 2 。

示例 2：

输入：nums = [10,10,10,3,1,1]

输出：4

解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：

组 1 -> [0]

组 2 -> [1,2]

组 3 -> [3]

组 4 -> [4,5]

分组方案满足题目要求的两个条件。

无法得到一个小于 4 组的答案。

所以答案为 4 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

思路：

题目要求我们求出最小的分组数目，首先我们可以确定的是，一个数组一定有答案，因为再不济把他每个元素都分一个组就可以了，又由于对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过1,假设我们分的所有的组的下标数量最小为k,那么最大也只能是k+1.

我们可以先用一个map存下每一个数出现的次数，对于每一个数it,出现的次数为cnt,我们看能否将这cnt个it分为只包含k个和k+1个的组。

假设数组中出现的最小次数的数目为mi,那么很容易得到k<=mi.如果k>mi,意味着至少有一组凑不够k个相同的数（同一组内所有下标在 nums 中对应的数值），所以我们可以遍历k(分的所有的组的下标数量最小值)，k确定了，k+1也就确定了。

对于每一个k,我们看nums里的所有数出现的次数能不能分为只包含k个和k+1个的组。

如果可以，我们就把当前k可以分得的最小组的数目求一个最小值ans.

如果不能那就。。。那就不能。

时间复杂读为什么是O(n)？

假设t表示的是nums数组中不同元素的个数，那么最小出现次数mi<=n/t,所以mi*t<=n.

O(min(mp[nums[i])*t)=O(mi*t)=O(n/t *t)=O(n)

这里计算时间复杂度非常重要哦，我开始也是算错了时间复杂度以为是o(n^2)了。、

代码：

class Solution {
public:
    int minGroupsForValidAssignment(vector<int>& nums) {
        map<int,int> mp;
        int len=nums.size();
        int mi=1e9+10;//最少出现次数
        for(auto it:nums){
            mp[it]++;//记录每个元素出现的次数
        }
        for(auto it:mp){
            mi=min(it.second,mi);
        }
        int ans=1e9;
        for(int k=1;k<=mi;k++){
            int tn=0;//记录当前k可以分得到的最小数目的组数
            int f=1;
            for(auto it:mp){
                int cnt=it.second;
                int a = cnt / (k + 1);
                int b = cnt - a * (k + 1);
                if (cnt % (k + 1) == 0) {//尽量拼元素多的组
                    tn += a;
                }
                else if (a + b >= k){//看能不能在a个（k+1）的组里面分诺干个1到剩下的b里面
                     tn += a + 1;
                }else{//优先拼k+1组失败了，退而求其次优先考虑拼k组
                     int a = cnt / (k );
                     int b = cnt - a * (k);
                     if(b>a){//如果剩下的元素b不能分到a个（k）组里面，说明分组失败
                         f=0;
                         break;
                     }
                     tn+=a;
                }
            }
           if(f) ans=min(ans,tn);
        }
 
        return ans;
    }
};