C++-এ দুটি সর্টেড লিস্টের মেডিয়ান বের করার প্রোগ্রাম

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

সমাধানের ধাপসমূহ:

• solve() ফাংশন ডিফাইন করুন যা দুটি অ্যারে nums1, nums2 নেবে
• যদি nums1.size() > nums2.size() হয়, তবে solve(nums2, nums1) কল করুন
• x := nums1.size(), y := nums2.size()
• low := 0, high := x
• totalLength := x + y
• while (low <= high):
  • partitionX := low + (high - low) / 2
  • partitionY := (totalLength + 1) / 2 - partitionX
  • maxLeftX := (partitionX == 0 ? INT_MIN : nums1[partitionX-1])
  • minRightX := (partitionX == x ? INT_MAX : nums1[partitionX])
  • maxLeftY := (partitionY == 0 ? INT_MIN : nums2[partitionY-1])
  • minRightY := (partitionY == y ? INT_MAX : nums2[partitionY])
  • যদি maxLeftX <= minRightY && maxLeftY <= minRightX হয়:
    • যদি totalLength % 2 == 0 হয়: return (max(maxLeftX,maxLeftY) + min(minRightX,minRightY)) / 2.0
    • অন্যথায়: return max(maxLeftX, maxLeftY)
  • অন্যথায় যদি maxLeftX > minRightY হয়: high = partitionX - 1
  • অন্যথায়: low = partitionX + 1
• return 0

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    double solve(vector<int>& nums1, vector<int>& 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;
    }
};

int main() {
    Solution ob;
    vector<int> v1 = {1, 5, 8}, v2 = {2, 3, 6, 9};
    cout << (ob.solve(v1, v2));
}

ইনপুট

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

আউটপুট

5