دروس جافا
ملف جافا

مقدمة

مشكلة العثور على الوسيط لمصفوفتين مفروزتين هي سؤال كلاسيكي في مقابلة الترميز. ويتمثل التحدي في العثور على الوسيط بكفاءة، مع تعقيد زمني قدره O(log(min(m, n)))، حيث m وn هما حجما المصفوفتين. في هذه المقالة، سنتعرف على حل Java الذي يستخدم البحث الثنائي لتحقيق هذه الكفاءة.

عرض المشكلة

بمعلومية المصفوفتين المرتبتين nums1 وnums2، أوجد الوسيط للمصفوفتين المفرزتين. يجب أن يكون التعقيد الإجمالي لوقت التشغيل هو O(log(min(m, n)))، حيث m وn هما حجم المصفوفتين.

يقترب

لحل هذه المشكلة، نستخدم أسلوب البحث الثنائي على أصغر المصفوفتين. الهدف هو تقسيم كلا المصفوفتين بحيث يحتوي النصف الأيسر على جميع العناصر الأقل من أو المساوية للعناصر الموجودة في النصف الأيمن. إليك شرح خطوة بخطوة:

1. تأكد من أن nums1 هو المصفوفة الأصغر: لتسهيل البحث الثنائي، تأكد من أن nums1 هو المصفوفة الأصغر.
2. إجراء بحث ثنائي: استخدم البحث الثنائي على nums1 للعثور على القسم الصحيح.
3. التقسيم: قم بتقسيم المصفوفتين بحيث يحتوي الجانب الأيسر على عناصر أقل، والجانب الأيمن يحتوي على عناصر أعلى.
4. حساب الوسيط: بناءً على الأقسام، احسب المتوسط.

حل

إليك تطبيق Java التفصيلي للحل:

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low  minY) {
                high = partitionX - 1;
            } else {
                low = partitionX   1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: "   solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

توضيح

1. التهيئة: تأكد من أن nums1 هو المصفوفة الأصغر.
2. البحث الثنائي: قم بإجراء بحث ثنائي على nums1 للعثور على القسم الصحيح.
3. حساب التقسيم والوسيط: احسب الحد الأقصى للعناصر اليسرى والحد الأدنى للعناصر اليمنى للعثور على الوسيط.

خاتمة

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