力扣100097. 合法分组的最少组数（哈希+贪心）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣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)了。、文章来源地址https://www.toymoban.com/news/detail-740149.html

代码：

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;
    }
};

到了这里，关于力扣100097. 合法分组的最少组数（哈希+贪心）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！