ধরুন আমাদের দুটি সাজানো তালিকা আছে। আমাদের এই দুটি তালিকার মধ্যক খুঁজে বের করতে হবে। তাই যদি অ্যারেগুলো হয় [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 ফেরত দিন
- যদি মোট দৈর্ঘ্য মোড 2 0 এর সমান হয়, তাহলে:
- অন্যথায় যখন 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