Python中将数组分割成递增序列

假设我们有一个非递减的正整数数组 nums 和一个整数 K，我们需要找出该数组是否可以被分成一个或多个不相交的长度至少为 K 的递增子序列。

因此，如果输入类似于 nums = [1,2,2,3,3,4,4]，K = 3，则输出为 true，因为该数组可以被分成两个子序列，例如 [1,2,3,4] 和 [2,3,4]，每个子序列的长度至少为 3。

为了解决这个问题，我们将遵循以下步骤：

• d := 一个新的映射

• req := 0

• 对于 nums 中的每个 i，执行：

  • 如果 i 不在 d 中，则

    • d[i]:= 1

  • 否则，

    • d[i] := d[i] + 1

  • 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

Arnab Chakraborty

更新于：2020年7月11日

166 次浏览

启动你的职业生涯

通过完成课程获得认证

开始学习