在Python中将数组划分为增加的序列
假设我们有一个非递减的正整数数组,称为nums和整数K,我们必须找出该数组是否可以划分为一个或多个长度不小于K的不相交的递增子序列。
因此,如果输入像nums=[1,2,2,3,3,4,4],K=3,那么输出将为true,因为此数组可以分为两个子序列,例如[1,2,3,4]和[2,3,4]各自的长度至少为3。
为了解决这个问题,我们将遵循以下步骤-
d:=新映射
要求:=0
对于每个以数字表示的i
d[i]:=d[i]+1
d[i]:=1
如果我不在d中为非零,则
除此以外,
req:=req的最大值,d[i]
当req*K<=nums的大小时返回true
让我们看下面的实现以更好地理解-
示例
class Solution(object): def canDivideIntoSubsequences(self, nums, K): d = {} req = 0 for i in nums: if i not in d: d[i]=1 else: d[i]+=1 req = max(req,d[i]) return req*K<=len(nums) ob = Solution()print(ob.canDivideIntoSubsequences([1,2,2,3,3,4,4],3))
输入值
[1,2,2,3,3,4,4]. 3
输出结果
True