C++ में दो क्रमबद्ध सरणियों का माध्यिका

मान लीजिए कि हमारे पास दो सरणियाँ हैं; इन सरणियों को क्रमबद्ध किया जाता है। अतः हमें इन दोनों सरणियों की माध्यिका ज्ञात करनी है। तो अगर सरणियाँ [1,5,8] और [2,3,6,9] जैसी हैं, तो उत्तर 5 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें FindMedianSortedArrays, इसमें nums1 और nums2 सरणियाँ लगेंगी

• अगर nums1 का आकार> nums2 का आकार, तो,

  • फ़ंक्शन को कॉल करें वापसी findMedianSortedArrays(nums2, nums1)

• x :=nums1 का आकार, y :=nums2 का आकार

• निम्न :=0, उच्च :=x

• कुल लंबाई :=x + y

• जबकि कम<=उच्च, करें −

  • पार्टीशनएक्स :=लो + (हाई-लो)/2

  • विभाजनवाई :=(कुल लंबाई + 1) / 2 - विभाजनX

  • maxLeftX =-inf जब पार्टीशनएक्स 0 है, अन्यथा nums1[partitionX-1]

  • maxRightX =inf जब पार्टीशनX x है, अन्यथा nums1[partitionX]

  • maxLeftY =-inf जब पार्टीशनवाई 0 है, अन्यथा nums2[partitionY-1]

  • maxRightY =inf जब पार्टीशनY y है, अन्यथा nums2[partitionY]

  • अगर maxLeftX<=minRightY और maxLeftY <=minRightX, तो,

    • अगर टोटल लेंथ मॉड 2 0 के समान है, तो,

      • वापसी (अधिकतम maxLeftX और maxLeftY) + न्यूनतम minRightX और minRightY) / 2

    • अन्यथा

      • maxLeftX और maxLeftY की अधिकतम वापसी करें

  • अन्यथा जब maxLeftX>minRightY, तब −

    • उच्च:=विभाजनX - 1

  • अन्यथा कम :=विभाजनX + 1

• वापसी 0

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   double findMedianSortedArrays(vector& 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[partitionX1] );
         int minRightX = (partitionX == x?INT_MAX :
         nums1[partitionX]);
         int maxLeftY = (partitionY ==0?INT_MIN:nums2[partitionY1] );
         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;
   }
};
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