Pythonで配列を増加するシーケンスに分割する

numsと呼ばれる正の整数と整数Kの非減少配列があるとすると、この配列を少なくともKの長さの1つ以上の互いに素な増加部分列に分割できるかどうかを調べる必要があります。

したがって、入力がnums =[1,2,2,3,3,4,4]、K =3のような場合、この配列は[1、 2,3,4]および[2,3,4]、それぞれ少なくとも3つの長さ。

これを解決するには、次の手順に従います-

• d：=新しいマップ

• req：=0

• numsの各iについて、実行します

  • dにないiがゼロ以外の場合、

    • d [i]：=1

  • それ以外の場合

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

  • req：=reqの最大値、d [i]

• req *K<=数値のサイズ

  の場合に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