حل سوال چهارم LeetCode

سلام دوستان عزیز، من مهدی شاملو هستم و خوشحالم که برگشتم با یک سوال Hard از LeetCode! 😎

این بار می‌خوام روش حل سوال چهارم LeetCode رو که یکی از سوالات معروف و چالش‌برانگیز بخش Hard هست، به اشتراک بذارم ( یکی از سوالاتی هست که در مصاحبه های فنی استخدامی خیلی پرسیده میشه )
مثل همیشه یادآوری می‌کنم که راه‌های مختلفی برای حل هر سوال وجود داره و راه‌حل بهینه‌تر (مثل O(log(m+n))) هم هست، اما این راه‌حلی هست که من پیاده کردم و ساده و قابل فهمه. امیدوارم براتون مفید باشه!

صورت سوال: Median of Two Sorted Arrays

دو آرایه مرتب شده nums1 و nums2 با اندازه‌های m و n به ما داده شده. باید میانه (median) آرایه ترکیبی این دو رو پیدا کنیم.

نکته مهم: پیچیدگی زمانی کلی باید O(log(m+n)) باشه (ولی راه‌حل من فعلاً ساده‌تره و O((m+n)log(m+n)) هست).

مثال‌ها:

Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 
توضیح: آرایه ترکیبی [1,2,3] → میانه ۲

Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000
 توضیح: آرایه ترکیبی [1,2,3,4] → میانه (۲ + ۳)/۲ = ۲.۵

محدودیت‌ها:

• اندازه هر آرایه تا ۱۰۰۰

• مجموع اندازه‌ها تا ۲۰۰۰

• اعداد بین -۱۰⁶ تا ۱۰⁶

راه‌حل من (رویکرد ساده با ادغام و مرتب‌سازی)

من از یک روش خیلی مستقیم استفاده کردم: دو آرایه رو با هم ادغام کردم، مرتب کردم و بعد میانه رو محاسبه کردم.

class Solution:
    def findMedianSortedArrays(self, nums1, nums2) -> float:
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        list3 = nums1 + nums2 # merge lists
        list3 = sorted(list3) # sort lists
        print(list3)
        mid = len(list3)/2
        print(f'mid is {mid}')
        print(f'mid is /2 {mid/2}')
        print(f'mid is /2 %2 {(mid / 2)%2}')

        if (len(list3))%2 == 0: # if number is not odd
            return (list3[int(mid)]+list3[int(mid-1)])/2
        else:
            return list3[int(mid)]

توضیح گام به گام:

۱. دو آرایه رو با + ادغام می‌کنیم → یک لیست جدید می‌سازیم.

۲. لیست جدید رو با sorted() مرتب می‌کنیم (چون آرایه‌های ورودی از قبل مرتب هستن، اما بعد از ادغام ممکنه نباشه).

۳. طول لیست ترکیبی رو نصف می‌کنیم تا اندیس وسط رو پیدا کنیم.

۴. اگر تعداد عناصر زوج باشه: میانگین دو عدد وسط رو برمی‌گردونیم.

۵. اگر فرد باشه: فقط عدد وسط رو برمی‌گردونیم.

این روش خیلی ساده و قابل فهمه و روی همه تست‌کیس‌های LeetCode پاس می‌شه، ولی پیچیدگی زمانی‌اش O((m+n)log(m+n)) هست به خاطر مرتب‌سازی.

نکته پایانی

می‌دونم که راه‌حل بهینه‌تر با الگوریتم Binary Search وجود داره که دقیقاً به پیچیدگی O(log(m+n)) می‌رسه و بدون ادغام کامل کار می‌کنه (خیلی هوشمندانه‌ست!). اگر کسی اون روش رو انجام داده یا راه‌حل بهتری داره، خیلی خوشحال می‌شم داخل کامنت‌ها یا گیت‌هابم بهم بگه تا یاد بگیرم و کدم رو آپدیت کنم 🚀

اگر سوالی داشتید یا نیاز به توضیح بیشتر بود، حتماً بپرسید که اگر بلد بودم کمک کنم

نویسنده: مهدی شاملو | Mahdi Shamlou