แบ่ง Array เป็นลำดับเพิ่มขึ้น (Increasing Sequences) ใน Python

สมมติว่าเรามีอาร์เรย์จำนวนเต็มบวกที่เรียงไม่ลดลง (non-decreasing) ชื่อ nums และจำนวนเต็ม K เราต้องตรวจสอบว่าอาร์เรย์นี้สามารถแบ่งเป็น subsequence ที่เพิ่มขึ้น (increasing) แยกจากกัน (disjoint) ได้หรือไม่ โดยแต่ละ subsequence ต้องมีความยาวอย่างน้อย K

เช่น nums = [1,2,2,3,3,4,4], K = 3 ผลลัพธ์คือ true เพราะแบ่งได้เป็น [1,2,3,4] และ [2,3,4] ความยาวอย่างน้อย 3 ทั้งคู่

วิธีแก้ (นับความถี่สูงสุด):

• นับความถี่ของแต่ละตัวเลขใน nums

• หาความถี่สูงสุด (req) = จำนวน subsequence ที่ต้องการขั้นต่ำ

• ถ้า req * K <= len(nums) แสดงว่าแบ่งได้ (เพราะแต่ละ subsequence ต้องมีอย่างน้อย K ตัว)

ตัวอย่างการใช้งาน

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