पायथन में कम से कम एक अद्वितीय तत्व वाली सूची में प्रत्येक उपन्यास की जाँच करने का कार्यक्रम

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

इसलिए, यदि इनपुट nums =[5, 10, 20, 10, 0] की तरह है, तो आउटपुट ट्रू होगा, क्योंकि अंकों में प्रत्येक सबलिस्ट में कम से कम एक तत्व होता है जो केवल एक बार हुआ है। [[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() । यह बाएँ, दाएँ ले जाएगा
• अगर बाएं>=दाएं, तो
  • सही लौटें
• गणना करता है:=एक शब्दकोश जिसमें अंकों में मौजूद प्रत्येक तत्व की आवृत्ति होती है [सूचकांक से बाएं से दाएं]
• यदि गिनती से न्यूनतम आवृत्ति> 1 है, तो
  • झूठी वापसी
• शुरू करें:=बाएं
• बाएं से दाएं श्रेणी में अनुक्रमणिका के लिए, करें
  • यदि मायने रखता है [nums[index]] 1 के समान है, तो
    • यदि has_unique(प्रारंभ, अनुक्रमणिका -1) गलत है, तो
      • झूठी वापसी
    • शुरू करें:=अनुक्रमणिका + 1
• वापसी has_unique(शुरू, दाएं)
• मुख्य विधि से, 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