C++ में दो सॉर्टेड ऐरे की माध्यिका

मान लीजिए हमारे पास दो ऐरे हैं; ये ऐरे सॉर्टेड हैं। इसलिए हमें इन दो ऐरे की माध्यिका ढूंढनी है। यदि ऐरे [1,5,8] और [2,3,6,9] हैं, तो उत्तर 5 होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• findMedianSortedArrays नामक एक फ़ंक्शन परिभाषित करें, जो nums1 और nums2 ऐरे लेता है
• यदि nums1 का आकार > nums2 का आकार, तो:
  • फंक्शन को वापस कॉल करें findMedianSortedArrays(nums2, nums1)
• x := nums1 का आकार, y := nums2 का आकार
• low := 0, high := x
• totalLength := x + y
• जब तक low <= high:
  • partitionX := low + (high - low) / 2
  • partitionY := (totalLength + 1) / 2 - partitionX
  • maxLeftX = -inf जब partitionX 0 हो, अन्यथा nums1[partitionX-1]
  • minRightX = inf जब partitionX x हो, अन्यथा nums1[partitionX]
  • maxLeftY = -inf जब partitionY 0 हो, अन्यथा nums2[partitionY-1]
  • minRightY = inf जब partitionY y हो, अन्यथा nums2[partitionY]
  • यदि maxLeftX <= minRightY और maxLeftY <= minRightX, तो:
    • यदि totalLength % 2 == 0, तो:
      • (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2 वापस करें
    • अन्यथा:
      • max(maxLeftX, maxLeftY) वापस करें
  • अन्यथा जब maxLeftX > minRightY, तो:
    • high := partitionX - 1
  • अन्यथा low := partitionX + 1
• 0 वापस करें

उदाहरण (C++ कोड)

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

#include <bits/stdc++.h> 
using namespace std; 
class Solution { 
public: 
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
        if(nums1.size() > nums2.size()) 
            return findMedianSortedArrays(nums2, nums1); 
        int x = nums1.size(); 
        int y = nums2.size(); 
        int low = 0; 
        int high = x; 
        int totalLength = x + y; 
        while(low <= high){ 
            int partitionX = low + (high - low) / 2; 
            int partitionY = (totalLength + 1) / 2 - partitionX; 
            int maxLeftX = (partitionX == 0 ? INT_MIN : nums1[partitionX - 1]); 
            int minRightX = (partitionX == x ? INT_MAX : nums1[partitionX]); 
            int maxLeftY = (partitionY == 0 ? INT_MIN : nums2[partitionY - 1]); 
            int minRightY = (partitionY == y ? INT_MAX : nums2[partitionY]); 
            if(maxLeftX <= minRightY && maxLeftY <= minRightX){ 
                if(totalLength % 2 == 0){ 
                    return ((double)max(maxLeftX, maxLeftY) + (double)min(minRightX, minRightY)) / 2; 
                } else { 
                    return max(maxLeftX, maxLeftY); 
                } 
            } 
            else if(maxLeftX > minRightY) 
                high = partitionX - 1; 
            else 
                low = partitionX + 1; 
        } 
        return 0; 
    } 
}; 
int main(){ 
    Solution ob; 
    vector<int> v1 = {1,5,8}, v2 = {2,3,6,9}; 
    cout << (ob.findMedianSortedArrays(v1, v2)); 
}

इनपुट

[1,5,8] [2,3,6,9]

आउटपुट

5