Python में जांचें कि सूची में प्रत्येक सबलिस्ट में कम से कम एक अद्वितीय तत्व है या नहीं

मान लीजिए हमारे पास nums नामक तत्वों की एक सूची है, हमें जांचना है कि क्या प्रत्येक सबलिस्ट में कम से कम 1 तत्व है जो उस सबलिस्ट में ठीक एक बार होता है या नहीं। हमें इस समस्या को रैखिक समय में हल करना है।

इसलिए, यदि इनपुट है nums = [5, 10, 20, 10, 0], तो आउटपुट True होगा, क्योंकि nums में प्रत्येक सबलिस्ट में कम से कम एक तत्व है जो केवल एक बार हुआ है। [[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]] सभी में कम से कम एक तत्व है जिसकी आवृत्ति 1 है।

हल करने का दृष्टिकोण

• has_unique() फ़ंक्शन परिभाषित करें। यह left, right लेगा
• यदि left >= right, तो true लौटाएं
• counts := nums[left से right तक इंडेक्स] में मौजूद प्रत्येक तत्व की आवृत्तियों वाला शब्दकोश
• यदि counts से न्यूनतम आवृत्ति > 1, तो false लौटाएं
• start := left
• left से right तक इंडेक्स के लिए, करें:
  • यदि counts[nums[index]] 1 के समान है, तो:
    • यदि has_unique(start, index - 1) false है, तो false लौटाएं
    • start := index + 1
• has_unique(start, right) लौटाएं
• मुख्य विधि से, has_unique(0, nums का आकार - 1) लौटाएं

उदाहरण

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

इनपुट

[5, 10, 20, 10, 0]

आउटपुट

True