本文主要是介绍力扣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 <= 1051 <= 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;}
};这篇关于力扣100097. 合法分组的最少组数（哈希+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
