পাইথনে ম্যাক্স ফ্রিকোয়েন্সি বিশিষ্ট উপাদান সমান ফ্রিকোয়েন্সি دار শর্টেস্ট সাবলিস্ট বের করা

একটি নম্বর লিস্ট nums দেওয়া আছে। সবচেয়ে বেশি ফ্রিকোয়েন্সি k। এমন সবচেয়ে ছোট সাবলিস্ট খুঁজুন যাতে এর মোস্ট ফ্রিকোয়েন্ট এলিমেন্টের ফ্রিকোয়েন্সিও k হয়।

ইনপুট উদাহরণ

nums = [10, 20, 30, 40, 30, 10]

আউটপুট: 3 (সাবলিস্ট [30, 40, 30]-এ ৩০-এর ফ্রিকোয়েন্সি ২ = k)

অ্যালগরিদম

1. ফ্রিকোয়েন্সি কাউন্ট করে mx (ম্যাক্স ফ্রিকোয়েন্সি) বের করুন।
2. যেসব এলিমেন্টের ফ্রিকোয়েন্সি mx, সেগুলো vs-এ রাখুন।
3. প্রতিটি v in vs-এর জন্য: first_occurrence এবং last_occurrence এর দূরত্ব + ১ = সাবলিস্ট লেংথ।
4. ন্যূনতম লেংথ রিটার্ন করুন।

পাইথন কোড

from collections import Counter

def solve(nums):
    L = len(nums)
    rnums = nums[::-1]
    d = Counter(nums)
    mx = max(d.values())
    vs = [k for k in d if d[k] == mx]
    mn = L
    for v in vs:
        mn = min(mn, (L - rnums.index(v)) - nums.index(v))
    return mn

# টেস্ট
print(solve([10, 20, 30, 40, 30, 10]))  # 3

ব্যাখ্যা

rnums.index(v) দিয়ে লাস্ট অকিউরেন্স, nums.index(v) দিয়ে ফার্স্ট অকিউরেন্স। সাবলিস্ট লেংথ = last - first + 1। সময় O(n)।