C++-এ দুটি সাজানো অ্যারের মধ্যমা

ধরুন আমাদের দুটি অ্যারে আছে; এই অ্যারে সাজানো হয়. তাই আমাদের এই দুটি অ্যারের মধ্যমা খুঁজে বের করতে হবে। তাই যদি অ্যারেগুলো হয় [1,5,8] এবং [2,3,6,9], তাহলে উত্তর হবে 5।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন FindMedianSortedArrays নির্ধারণ করুন, এটি nums1 এবং nums2 অ্যারে নেবে

• যদি সংখ্যা 1 এর আকার> সংখ্যা 2 এর আকার, তাহলে,

  • ফাংশন রিটার্ন findMedianSortedArrays(nums2, nums1)

• x :=সংখ্যা 1 এর আকার, y :=সংখ্যা 2 এর আকার

• কম :=0, উচ্চ :=x

• মোট দৈর্ঘ্য :=x + y

• যখন কম<=উচ্চ, করুন −

  • partitionX :=নিম্ন + (উচ্চ - নিম্ন) / 2

  • partitionY :=(মোট দৈর্ঘ্য + 1) / 2 - partitionX

  • maxLeftX =-inf যখন partitionX 0 হয়, অন্যথায় nums1[partitionX-1]

  • maxRightX =inf যখন partitionX হয় x, অন্যথায় nums1[partitionX]

  • maxLeftY =-inf যখন partitionY 0 হয়, অন্যথায় nums2[partitionY-1]

  • maxRightY =inf যখন partitionY y হয়, অন্যথায় nums2[partitionY]

  • যদি maxLeftX<=minRightY এবং maxLeftY <=minRightX, তাহলে,

    • যদি মোট দৈর্ঘ্য মোড 2 0 এর সমান হয়, তাহলে,

      • রিটার্ন (সর্বোচ্চ maxLeftX এবং maxLeftY) + সর্বনিম্ন minRightX এবং minRightY) / 2

    • অন্যথায়

      • সর্বাধিক maxLeftX এবং maxLeftY

        ফেরত দিন

  • অন্যথায় যখন maxLeftX>minRightY, তারপর −

    • উচ্চ :=partitionX - 1

  • অন্যথায় কম :=partitionX + 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