C++ এ দুটি সাজানো তালিকার মধ্যক খুঁজে বের করার প্রোগ্রাম

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

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

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি একটি অ্যারে সংখ্যা 1, একটি অ্যারে সংখ্যা2,
• যদি সংখ্যা 1 এর আকার> সংখ্যা 2 এর আকার, তারপর:
  • রিটার্ন সমাধান (সংখ্যা2, সংখ্যা1)
• x :=সংখ্যা 1 এর আকার, y :=সংখ্যা 2 এর আকার
• নিম্ন :=0, উচ্চ :=x
• মোট দৈর্ঘ্য :=x + y
• যখন কম <=উচ্চ, করবেন:
  • partitionX :=low + (উচ্চ - নিম্ন)
  • partitionY :=(মোট দৈর্ঘ্য + 1) / 2 - partitionX
  • maxLeftX :=(যদি partitionX 0 এর মত হয়, তাহলে -inf, অন্যথায় nums1[partitionX - 1])
  • minRightX :=(যদি partitionX x এর মত হয়, তাহলে inf, অন্যথায় nums1[partitionX])
  • maxLeftY :=(যদি partitionY 0 এর মত হয়, তাহলে -inf, অন্যথায় nums2[partitionY - 1])
  • minRightY :=(যদি partitionY y এর মত হয়, তাহলে inf, অন্যথায় nums2[partitionY])
  • যদি maxLeftX <=minRightY এবং maxLeftY <=minRightX, তাহলে:
    • যদি মোট দৈর্ঘ্য মোড 2 0 এর সমান হয়, তাহলে:
      • রিটার্ন (সর্বোচ্চ maxLeftX এবং maxLeftY) + (ন্যূনতম minRightX এবং minRightY))/ 2
    • অন্যথায়
      • সর্বোচ্চ maxLeftX এবং maxLeftY ফেরত দিন
  • অন্যথায় যখন maxLeftX> minRightY, তারপর:
    • উচ্চ :=partitionX - 1
  • অন্যথায়
• রিটার্ন 0

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

#include
using namespace std;

class Solution {
   public:
   double solve(vector& nums1, vector& nums2) {
      if(nums1.size()>nums2.size())
         return solve(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;
   }
};
main(){
   Solution ob;
   vector v1 = {1,5,8}, v2 = {2,3,6,9};
   cout << (ob.solve(v1, v2));
}

ইনপুট

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

আউটপুট

5