快速模板建站工具,杭州做网站价格,天津工程信息网,成都信用网企业查询系统目录 元素和最小的山形三元组 I元素和最小的山形三元组 II合法分组的最少组数 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。 如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个山形三元组 #xff1a; i j k nums[i] 则认为它是一个山形三元组 i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出nums中元素和最小的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。
示例 1 输入nums [8,6,1,5,3] 输出9 解释三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组因为 2 3 4nums[2] nums[3] 且 nums[4] nums[3] 这个三元组的元素和等于 nums[2] nums[3] nums[4] 9 。可以证明不存在元素和小于 9 的山形三元组。 示例 2 输入nums [5,4,8,7,10,2] 输出13 解释三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组因为 1 3 5nums[1] nums[3] 且 nums[5] nums[3] 这个三元组的元素和等于 nums[1] nums[3] nums[5] 13 。可以证明不存在元素和小于 13 的山形三元组。 示例 3 输入nums [6,5,4,3,4,5] 输出-1 解释可以证明 nums 中不存在山形三元组。 提示 3 n u m s . l e n g t h 50 3 nums.length 50 3nums.length50 1 n u m s [ i ] 50 1 nums[i] 50 1nums[i]50
分析 因为数据范围很小所以可以直接按照题目意思进行模拟遍历每一个三元组维护一个最小三元组的和即可。时间复杂度 O ( n 3 ) O(n^3) O(n3)。 代码
class Solution {
public:int minimumSum(vectorint nums) {int nnums.size();int ansINT_MAX;for(int i0;in;i){for(int ji1;jn;j){for(int kj1;kn;k){if(nums[i]nums[j]nums[k]nums[j])ansmin(ans,nums[i]nums[j]nums[k]);}}}if(ansINT_MAX)ans-1;return ans;}
};元素和最小的山形三元组 II
给你一个下标从 0 开始的整数数组 nums 。 如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个山形三元组 i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出nums中元素和最小的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。
示例 1 输入nums [8,6,1,5,3] 输出9 解释三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组因为 2 3 4nums[2] nums[3] 且 nums[4] nums[3] 这个三元组的元素和等于 nums[2] nums[3] nums[4] 9 。可以证明不存在元素和小于 9 的山形三元组。 示例 2 输入nums [5,4,8,7,10,2] 输出13 解释三元组 (1, 3, 5) 是一个元素和等于 13 的山形三元组因为 1 3 5nums[1] nums[3] 且 nums[5] nums[3] 这个三元组的元素和等于 nums[1] nums[3] nums[5] 13 。可以证明不存在元素和小于 13 的山形三元组。 示例 3 输入nums [6,5,4,3,4,5] 输出-1 解释可以证明 nums 中不存在山形三元组。 提示 3 n u m s . l e n g t h 1 0 5 3 nums.length 10^{5} 3nums.length105 1 n u m s [ i ] 1 0 8 1 nums[i] 10^{8} 1nums[i]108
分析 本题为第一题的加强版数据范围扩大使用题一的 O ( n 3 ) O(n^3) O(n3)的方法会TLE所以我们仔细思考题意不难想到要使得一个三元组的和最小那么对于山顶i找到i左边的最小值pre[i]和i右边的最小值suf[i]只要pre[i]和suf[i]同时都小于nums[i]的值那么这就是以i为山顶的三元组的和的最小值。 所以我们可以先进行预处理遍历一遍数组维护一个前缀最小值和后缀最小值。时间复杂度为 O ( n ) O(n) O(n) 代码
class Solution {
public:int minimumSum(vectorint nums) {//对每个数找到其前面的最小数和后面的最小数int n nums.size();vectorintpre(n1),suf(n1);pre[0]nums[0];suf[n-1]nums[n-1];for(int i1;in;i)pre[i]min(nums[i],pre[i-1]);for(int in-2;i0;i--)suf[i]min(nums[i],suf[i1]);int ansINT_MAX;for(int i0;in;i){if(nums[i]pre[i]nums[i]suf[i])ansmin(ans,pre[i]nums[i]suf[i]);}if(ansINT_MAX)ans-1;return ans;}
};合法分组的最少组数
给你一个长度为 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 n u m s . l e n g t h 1 0 5 1 nums.length 10^{5} 1nums.length105 1 n u m s [ i ] 1 0 9 1 nums[i] 10^{9} 1nums[i]109
分析 首先我们需要统计每个数字出现的次数维护在cnt中。 如何判断一个数字可以拆分为k和k1的组合呢 比如说cnt[x]13k4那么134441多出来的这一个1可以丢进前面的某一个4中同理11443不能由k和k1构成144442554154443555而164444不能由5表示了可以想到只要cnt[x]/k的值大于等于cnt[x]%k的值那么其就可以由k和k1来构成。 那么如何计算最小的分组呢 不难理解只要分出的k1越多那么分出的组数肯定就越少即最少可以分出 ⌈ c n t [ x ] k 1 ⌉ \lceil \frac{cnt[x]}{k1} \rceil ⌈k1cnt[x]⌉个组。 因为我们已经确定了能够拆分为k和k1的组合pcnt[x]/kvcnt[x]%k先拆成了p个k剩下数字v其实就是v有几个那么就可以将多少个v个k加一变成k1。所以直接除以k1即可得到组数上取整是因为如果除以k1有余数那么这个余数需要补充到有k个数即组数会多一个。 比如15555165551444413553544。 最后只需要从min(cnt[x])开始往下枚举k找到一个满足要求的k即可返回结果。 时间复杂度枚举cnt中最小的数为kcnt的size为m m k ≤ n mk \le n mk≤n循环的次数最多为km所以时间复杂度为 O ( n ) O(n) O(n)。 代码
class Solution {
public:int minGroupsForValidAssignment(vectorint nums) {int n nums.size();unordered_mapint, intmp;vectorintcnt;for(int i 0; i n ; i){mp[nums[i]];}for(auto [k,v]:mp)cnt.push_back(v);sort(cnt.begin(),cnt.end());int min_numcnt[0];//枚举最小的组do{int ans 0;if(min_num0)break;for(auto x:cnt){int p x / min_num;int v x % min_num;if(p v)ans (x min_num) / (min_num 1);else{ans 0;break;}}if(ans)return ans;}while(min_num--);return 0;}};
