JAVA ट्यूटोरियल
जावा फ़ाइल

परिचय

दो क्रमबद्ध सरणियों का माध्य खोजने की समस्या एक क्लासिक कोडिंग साक्षात्कार प्रश्न है। चुनौती O(log(min(m, n))) की समय जटिलता के साथ, कुशलतापूर्वक माध्यिका को खोजने की है, जहां m और n दो सरणियों के आकार हैं। इस लेख में, हम एक जावा समाधान के बारे में जानेंगे जो इस दक्षता को प्राप्त करने के लिए बाइनरी खोज को नियोजित करता है।

समस्या का विवरण

दो क्रमबद्ध सरणियों संख्या1 और अंक2 को देखते हुए, दो क्रमबद्ध सरणियों का माध्य ज्ञात कीजिए। समग्र रनटाइम जटिलता O(log(min(m, n))) होनी चाहिए, जहां m और n दो सरणियों के आकार हैं।

दृष्टिकोण

इस समस्या को हल करने के लिए, हम दो सरणियों में से छोटे पर बाइनरी खोज दृष्टिकोण का उपयोग करते हैं। लक्ष्य दोनों सरणियों को इस तरह विभाजित करना है कि बाएं आधे हिस्से में सभी तत्व दाएं आधे के तत्वों से कम या बराबर हों। यहां चरण-दर-चरण स्पष्टीकरण दिया गया है:

1. सुनिश्चित करें कि अंक1 छोटी सरणी है: आसान बाइनरी खोज के लिए, सुनिश्चित करें कि संख्या1 छोटी सरणी है।
2. बाइनरी खोज करें: सही विभाजन ढूंढने के लिए अंक1 पर बाइनरी खोज का उपयोग करें।
3. विभाजन: दोनों सरणियों को इस तरह विभाजित करें कि बाईं ओर निचले तत्व हों, और दाईं ओर उच्च तत्व हों।
4. माध्यिका की गणना करें: विभाजनों के आधार पर, माध्यिका की गणना करें।

समाधान

यहां समाधान का विस्तृत जावा कार्यान्वयन है:

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. प्रारंभीकरण: सुनिश्चित करें कि संख्या1 छोटी सरणी है।
2. बाइनरी खोज: सही विभाजन ढूंढने के लिए अंक1 पर बाइनरी खोज करें।
3. विभाजन और माध्यिका गणना: माध्यिका ज्ञात करने के लिए बाएँ तत्वों की अधिकतम और दाएँ तत्वों की न्यूनतम की गणना करें।

निष्कर्ष

यह द्विआधारी खोज दृष्टिकोण दो क्रमबद्ध सरणियों के माध्यिका को खोजने के लिए एक कुशल समाधान प्रदान करता है। छोटे ऐरे पर बाइनरी खोज का लाभ उठाकर, समाधान O(log(min(m, n))) की समय जटिलता प्राप्त करता है, जिससे यह बड़े इनपुट ऐरे के लिए उपयुक्त हो जाता है।