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

贪心）"/>

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