Median of Two Sorted Arrays

Q: ما هو التعقيد الزمني لإيجاد الوسيط في مصفوفتين مرتبتين؟

يستغرق البحث الثنائي عن موضع الفصل O(log(min(m, n))) من الوقت و O(1) من المساحة، لأن كل خطوة تقلّص إلى النصف عدد مواضع الفصل المحتملة في القائمة الأقصر. أما الدمج فيستغرق O(m + n) : لقائمتين من 3000 عنصر، يستغرق البحث نحو 12 خطوة بدلًا من 6000.

Q: لماذا نُجري البحث الثنائي على المصفوفة الأقصر؟

لأن j = half-i . عندما تكون i ضمن القائمة الأقصر، تبقى j بين 0 وطول القائمة الأطول، لذا تكون كل قراءة ضمن النطاق أو بعد نهاية تتعامل معها على أنها ما لا نهاية.

صعبالبحث الثنائي

+10

تحصل على قائمتين من الأعداد الصحيحة، nums1 وnums2، وكلتاهما مرتبة من الأصغر إلى الأكبر وتحتويان على قيمة واحدة على الأقل. أعد وسيط جميع القيم فيهما معًا، كنص.

إذا كان العدد الإجمالي فرديًا، فالوسيط هو القيمة الوسطى، مثل "4". وإذا كان العدد زوجيًا، فهو متوسط القيمتين الوسطيتين، مثل "2.5" أو "-0.5". اكتب العدد الصحيح من دون فاصلة عشرية، واكتب الصفر على صورة "0"، وليس أبدًا "-0". اسعَ إلى تحقيق زمن قدره O(log(min(m, n))).

الدالة

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: القائمة الأولى، مرتبة من الأصغر إلى الأكبر
nums2integer-array: القائمة الثانية، مرتبة من الأصغر إلى الأكبر
تُرجعstring: الوسيط لجميع القيم، كنص مثل "4" أو "-2.5"

القيود

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
كلتا القائمتين مرتبتان بترتيب غير تنازلي، وقد تتكرر القيم.

أمثلة

المدخلات: nums1 = [1, 4]nums2 = [2, 7, 9]
المخرجات: "4"
الشرح: القيم معًا هي 1، 2، 4، 7، 9. للقيم الخمس قيمة وسطى واحدة، وهي الثالثة، وتساوي 4.

سؤال إضافي

هل يمكنك استخدام القطع نفسه لإيجاد القيمة رقم k من الأصغر في القائمتين، لأي k، في زمن لوغاريتمي؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يؤدي دمج القائمتين إلى إيجاد الوسيط في O(m + n)، لكن معظم القيم التي يقرأها لا يمكنها تغيير الإجابة. يعتمد الوسيط فقط على موضع القطع بين النصف الأدنى والنصف الأعلى، ويحدد عددٌ واحد هذا القطع: عدد القيم التي يأخذها النصف الأدنى من القائمة الأقصر. يعثر البحث الثنائي عليه في O(log(min(m, n))) خطوات.

ادمج القائمتين

الفكرة

ادمج القائمتين بالطريقة التي تستخدمها خوارزمية ترتيب الدمج، لتكوين قائمة واحدة مرتبة merged. مع total = m + n، اجمع merged[(total-1)/2] وmerged[total/2]، باستخدام القسمة الصحيحة. إذا كان المجموع فرديًا، فالقيمتان كلتاهما هما القيمة الوسطى، وإذا كان زوجيًا، فهما القيمتان الوسطيتان؛ لذا فإن نصف المجموع هو الوسيط في كلتا الحالتين.

حتى لو توقفت عند المنتصف، فإن خطوات الدمج تمر على أكثر من نصف القيم، لذا يكون الزمن O(m + n).

الخوارزمية

ادمج القائمتين في merged، مع اختيار القيمة الحالية الأصغر دائمًا، ثم أضف بقية القائمة التي لم تنتهِ.
باستخدام total = m + n، اجمع merged[(total-1)/2] وmerged[total/2].
أعِد نصف المجموع كنص: اقسم المجموع الزوجي على 2؛ أما إذا كان فرديًا، فاكتب الإشارة ونصف القيمة المطلقة و.5.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

البحث الثنائي عن موضع الفصل

الفكرة

لنجعل النصف الأدنى يحتوي على half = (m+n+1)/2 قيمة، مع قيمة إضافية واحدة عندما يكون المجموع فرديًا. يأخذ i قيمة من مقدمة nums1 وj = half-i من مقدمة nums2. يكون موضع القطع صحيحًا عندما لا يكون أي عنصر أسفله أكبر من أي عنصر أعلاه. كل قائمة مرتبة، لذا يتبقى التحقق من شرطين: left1 ≤ right2 وleft2 ≤ right1، حيث تمثل left آخر قيمة تمنحها القائمة للنصف الأدنى، وتمثل right أول قيمة تحتفظ بها. ويُعد الجانب المفقود سالب ما لا نهاية أو موجب ما لا نهاية.

إذا كان left1 > right2، فإن i كبير جدًا؛ وإذا كان left2 > right1، فهو صغير جدًا. لذا يكون i موضع بحث ثنائي بين 0 وm. في [1, 2] و[3, 4]، لا ينجح i = 1 بسبب left2 = 3 > right1 = 2، وينجح i = 2: (2 + 3) / 2 = 2.5.

الخوارزمية

اجعل nums1 القائمة الأقصر؛ ولتكن half = (m+n+1)/2.
ابحث بحثًا ثنائيًا عن i من lo = 0 إلى hi = m، مع j = half-i.
اقرأ left1 = nums1[i-1] وright1 = nums1[i] وleft2 = nums2[j-1] وright2 = nums2[j]، مع اعتبار القيمة بعد نهاية القائمة ما لا نهاية.
إذا كان left1 > right2، فعيّن hi = i-1. وإذا كان left2 > right1، فعيّن lo = i+1.
وإلا، فأعِد max(left1, left2) إذا كان المجموع فرديًا. وإذا كان المجموع زوجيًا، فاقسم max(left1, left2) + min(right1, right2) على اثنين كنص.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

أخطاء شائعة وحالات حدّية

القسمة إلى النصف باستخدام الأعداد العشرية. تطبع Python الوسيط الصحيح على هيئة 3.0، وتطبع %f في C العدد 2.5 على هيئة 2.500000. اجعل المجموع عددًا صحيحًا.
كتابة خارج القسمة الصحيحة و.5 لمجموع فردي سالب. تكون نتيجة -1 / 2 هي 0 في C وJava، ما يعطي 0.5 بدلًا من -0.5؛ وتكون نتيجة -5 // 2 هي -3 في Python، ما يعطي -3.5 بدلًا من -2.5. اقسم القيمة المطلقة على 2، ثم أعد الإشارة.
كتابة -0. مجموع القيمتين الوسطيتين -1 و1 يساوي 0، والإجابة هي "0". خذ الإشارة من المجموع.
البحث في القائمة الأطول. قد تكون قيمة j = half-i أقل من 0 أو أكبر من n. بدّل القائمتين أولًا.
قراءة nums1[i-1] عندما تكون i = 0، كما في [9] و[1, 2]. استخدم قيم اللانهاية للقيم المفقودة.

أسئلة شائعة3

ما هو التعقيد الزمني لإيجاد الوسيط في مصفوفتين مرتبتين؟

يستغرق البحث الثنائي عن موضع الفصل O(log(min(m, n))) من الوقت وO(1) من المساحة، لأن كل خطوة تقلّص إلى النصف عدد مواضع الفصل المحتملة في القائمة الأقصر. أما الدمج فيستغرق O(m + n): لقائمتين من 3000 عنصر، يستغرق البحث نحو 12 خطوة بدلًا من 6000.

لماذا نُجري البحث الثنائي على المصفوفة الأقصر؟

لأن j = half-i. عندما تكون i ضمن القائمة الأقصر، تبقى j بين 0 وطول القائمة الأطول، لذا تكون كل قراءة ضمن النطاق أو بعد نهاية تتعامل معها على أنها ما لا نهاية.

كيف تُرجع الوسيط من دون استخدام الأعداد ذات الفاصلة العائمة؟

اجمع القيمتين الوسطيتين كعددين صحيحين. اقسم المجموع الزوجي على 2. إذا كان المجموع فرديًا، فاكتب نصف قيمته المطلقة و.5، مع إشارة سالبة عندما يكون المجموع سالبًا: يصبح -1 "-0.5".

def findMedianSortedArrays(nums1, nums2):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

nums1 = [1, 4]
nums2 = [2, 7, 9]

الإخراج المتوقع

"4"