Pythonで配列を長さK以上の増加部分列に分割できるか判定する方法

問題の概要

正の整数からなる非減少配列（広義単調増加の配列） nums と整数 K が与えられます。このとき、配列全体を「長さが K 以上の互いに重複しない（disjoint な）増加部分列」に 1 つ以上分割できるかどうかを判定するのが目的です。

入力例と出力例

nums = [1,2,2,3,3,4,4]、K = 3 の場合、答えは true になります。実際、この配列は [1,2,3,4] と [2,3,4] という 2 つの部分列に分割でき、どちらも長さが 3 以上であるため条件を満たします。

解き方のポイント

鍵となるのは「同じ値は 1 つの増加部分列に 2 度現れない」という性質です。最も出現回数の多い値の出現回数を req とすると、その値をすべて異なる部分列に振り分ける必要があるため、少なくとも req 個の部分列が必要になります。さらに各部分列の長さは K 以上でなければならないので、必要な要素の総数は req × K 以上です。

したがって、次の条件が成り立つ場合に限り、答えは true となります。

req * K <= len(nums)

逆にこの条件を満たしていれば、要素を順番に各部分列へ割り振ることで必ず分割できることが示せるため、この判定だけで十分です。

アルゴリズムの手順

• 各要素の出現回数を数えるための辞書（マップ）d を用意する
• 最大出現回数を保持する変数 req を 0 で初期化する
• nums の各要素 i について次を行う
  • i が d に存在しなければ d[i] = 1 とする
  • 存在すれば d[i] += 1 とする
  • req を max(req, d[i]) で更新する
• req * K <= len(nums) なら true を返す

Pythonでの実装例

なお、すべての要素が 1 回しか現れないケース（K が配列長より大きい場合など）でも正しく判定できるよう、req の更新処理は if / else の外側に配置しています。

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))

より簡潔な書き方（collections.Counter を利用）

from collections import Counter

class Solution(object):
    def canDivideIntoSubsequences(self, nums, K):
        req = max(Counter(nums).values())
        return req * K <= len(nums)

入力

[1,2,2,3,3,4,4], 3

出力

True

計算量

• 時間計算量： O(n) ― 配列を一度走査して各要素の出現回数を数えるだけで済みます。
• 空間計算量： O(n) ― 出現回数を格納する辞書が必要です。