免费大气网站模板,河南周口东宇网站建设,网站设计资料,电脑版qq在线登录网页入口文章目录1. 题目2. 解题1. 题目
给你一个 非递减 的正整数数组 nums 和整数 K#xff0c;判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。
示例 1#xff1a;
输入#xff1a;nums [1,2,2,3,3,4,4], K 3
输出#xff1a;true
解释#xff…
文章目录1. 题目2. 解题1. 题目
给你一个 非递减 的正整数数组 nums 和整数 K判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。
示例 1
输入nums [1,2,2,3,3,4,4], K 3
输出true
解释
该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]
每个子序列的长度都至少是 3。示例 2
输入nums [5,6,6,7,8], K 3
输出false
解释
没有办法根据条件来划分数组。提示
1 nums.length 10^5
1 K nums.length
1 nums[i] 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/divide-array-into-increasing-sequences 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目要求每个子序列严格递增所以每个子序列里没有相同的值找出数组里出现次数最多的c 次这个数分给 c 个子序列每个子序列长度至少为 K那么必须满足 c∗Knc*K nc∗Kn 数组长度
class Solution {
public:bool canDivideIntoSubsequences(vectorint nums, int K) {unordered_mapint,int count;int i, maxcount 0, n nums.size();for(i 0; i n; i){count[nums[i]];maxcount max(maxcount, count[nums[i]]);}return maxcount*K n;}
};584 ms 103.7 MB
数组有序不需要哈希map计数见官方答案
class Solution {
public:bool canDivideIntoSubsequences(vectorint nums, int K) {int pre nums[0], cnt 0;for (int n : nums) {if (n pre)cnt;else {pre n;cnt 1;}if (cnt * K nums.size())return false;}return true;}
};284 ms 69.2 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
