โปรแกรมตรวจสอบทุก sublist มีสมาชิกเฉพาะตัวอย่างน้อยหนึ่งตัวใน Python

คำอธิบายปัญหา

กำหนดลิสต์ nums ตรวจสอบว่า **ทุก sublist** มีองค์ประกอบอย่างน้อย 1 ตัวที่เกิดขึ้นเพียงครั้งเดียวใน sublist นั้น (unique element) ต้องแก้ใน O(n) time

ตัวอย่าง

nums = [5, 10, 20, 10, 0] → Output: True

ทุก sublist 15 ชุด มี element ที่ frequency = 1 อย่างน้อย 1 ตัว

ขั้นตอนการแก้ปัญหา (Divide & Conquer)

1. ฟังก์ชัน has_unique(left, right) ตรวจสอบช่วง nums[left:right+1]
2. นับความถี่ในช่วง → หากค่าต่ำสุด > 1 คืน False
3. หาตำแหน่งที่มีค่า unique (freq=1) แบ่งปัญหาเป็นส่วนซ้ายและขวา เรียกซ้ำ

การตนการทำงาน (Python)

from collections import Counter

def solve(nums):
    def has_unique(left, right):
        if left >= right:
            return True
        counts = Counter(nums[left:right+1])
        if min(counts.values()) > 1:
            return False
        start = left
        for index in range(left, right + 1):
            if counts[nums[index]] == 1:
                if not has_unique(start, index - 1):
                    return False
                start = index + 1
        return has_unique(start, right)
    return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))  # Output: True

อินพุต / เอาต์พุต

Input:  [5, 10, 20, 10, 0]
Output: True