ধরুন আমাদের দুটি অ্যারে আছে; এই অ্যারে সাজানো হয়. তাই আমাদের এই দুটি অ্যারের মধ্যমা খুঁজে বের করতে হবে। তাই যদি অ্যারেগুলো হয় [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