代理国外网站,广州网站整站优化,自己的网站怎么做进销存,微信小程序开发用什么工具题目描述#xff1a;
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组#xff0c;使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立#xff0c;我们说这个分组方案是合法的#xff1a;
对于每个组 g #xff0c;同一…题目描述
给你一个长度为 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,那么最大也只能是k1.
我们可以先用一个map存下每一个数出现的次数对于每一个数it,出现的次数为cnt,我们看能否将这cnt个it分为只包含k个和k1个的组。
假设数组中出现的最小次数的数目为mi,那么很容易得到kmi.如果kmi,意味着至少有一组凑不够k个相同的数同一组内所有下标在 nums 中对应的数值所以我们可以遍历k(分的所有的组的下标数量最小值)k确定了k1也就确定了。
对于每一个k,我们看nums里的所有数出现的次数能不能分为只包含k个和k1个的组。
如果可以我们就把当前k可以分得的最小组的数目求一个最小值ans.
如果不能那就。。。那就不能。
时间复杂读为什么是O(n)
假设t表示的是nums数组中不同元素的个数那么最小出现次数min/t,所以mi*tn. O(min(mp[nums[i])*t)O(mi*t)O(n/t *t)O(n) 这里计算时间复杂度非常重要哦我开始也是算错了时间复杂度以为是o(n^2)了。、
代码
class Solution {
public:int minGroupsForValidAssignment(vectorint nums) {mapint,int mp;int lennums.size();int mi1e910;//最少出现次数for(auto it:nums){mp[it];//记录每个元素出现的次数}for(auto it:mp){mimin(it.second,mi);}int ans1e9;for(int k1;kmi;k){int tn0;//记录当前k可以分得到的最小数目的组数int f1;for(auto it:mp){int cntit.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个k1的组里面分诺干个1到剩下的b里面tn a 1;}else{//优先拼k1组失败了退而求其次优先考虑拼k组int a cnt / (k );int b cnt - a * (k);if(ba){//如果剩下的元素b不能分到a个k组里面说明分组失败f0;break;}tna;}}if(f) ansmin(ans,tn);}return ans;}
};
