Chia mảng thành các dãy con tăng dần trong Python

Cho mảng không giảm nums (số nguyên dương) và số nguyên K. Kiểm tra xem có thể chia mảng thành một hoặc nhiều dãy con tăng dần rời rạc, mỗi dãy độ dài ít nhất K.

Ví dụ: nums=[1,2,2,3,3,4,4], K=3 → True (chia thành [1,2,3,4] và [2,3,4], mỗi dãy độ dài ≥3).

Giải thuật

• Đếm tần suất xuất hiện tối đa của bất kỳ số nào (req)
• Cần ít nhất req dãy con để chứa các bản sao của số xuất hiện nhiều nhất
• Mỗi dãy cần ít nhất K phần tử → tổng cần req * K ≤ len(nums)

Ví dụ triển khai

class Solution:
    def canDivideIntoSubsequences(self, nums, K):
        d = {}
        req = 0
        for x in nums:
            if x not in d:
                d[x] = 1
            else:
                d[x] += 1
            req = max(req, d[x])
        return req * K <= len(nums)

ob = Solution()
print(ob.canDivideIntoSubsequences([1, 2, 2, 3, 3, 4, 4], 3))

Đầu vào

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

Đầu ra

True