โปรแกรมแบ่งรายการเป็นสับลิสต์เพิ่มขึ้นอย่างเคร่งครัดขนาดมากกว่า k ใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราต้องตรวจสอบว่าสามารถแบ่งรายการเป็น sublists ได้หรือไม่ โดยแต่ละ sublist ต้องมีความยาว ≥ k และเป็น strictly increasing (ไม่ต้องติดกันในรายการเดิม)

เช่น ถ้าข้อมูลนำเข้าคือ nums = [6, 7, 5, 10, 13] k = 2 ผลลัพธ์จะเป็น True เนื่องจากแบ่งได้เป็น [5, 6] และ [7, 10, 13]

ขั้นตอนการแก้ปัญหา (Pigeonhole Principle)

• c := Counter(nums)
• max_count := ความถี่สูงสุดใน c
• คืน True ถ้า max_count * k <= len(nums) มิฉะนั้น False

เหตุผล: ค่าที่ซ้ำมากที่สุดต้องกระจายไปใน sublists ต่างกัน หากต้องการแต่ละ sublist ยาว ≥ k ต้องมีที่ว่างพอ

ตัวอย่างโค้ด

from collections import Counter
class Solution:
    def solve(self, nums, k):
        c = Counter(nums)
        max_count = max([v for k, v in c.items()])
        return max_count * k <= len(nums)

ob = Solution()
nums = [6, 7, 5, 10, 13]
k = 2
print(ob.solve(nums, k))

ข้อมูลนำเข้า

[6, 7, 5, 10, 13], 2

ผลลัพธ์

False