পাইথনে অন্তত একটি অনন্য উপাদান সমন্বিত একটি তালিকার প্রতিটি সাবলিস্ট পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে 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() সংজ্ঞায়িত করুন। এটি বাম, ডান
নিয়ে যাবে
• বামে থাকলে>=ডানে, তারপর
  • সত্য ফেরান
• গণনা :=সংখ্যায় উপস্থিত প্রতিটি উপাদানের ফ্রিকোয়েন্সি সম্বলিত একটি অভিধান [সূচী বাম থেকে ডানে]
• যদি গণনা থেকে ন্যূনতম ফ্রিকোয়েন্সি> 1 হয়, তাহলে
  • মিথ্যে ফেরত দিন
• শুরু :=বাকি
• বাম থেকে ডান পরিসরে সূচকের জন্য, করুন
  • যদি গণনা [সংখ্যা[সূচক]] 1 এর মত হয়, তাহলে
    • যদি has_unique(start, index - 1) মিথ্যা হয়, তাহলে
      • মিথ্যে ফেরত দিন
    • শুরু :=সূচক + 1
• রিটার্ন has_unique(শুরু, ডানে)
• প্রধান পদ্ধতি থেকে, রিটার্ন has_unique(0, সংখ্যার আকার - 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