C++ में दो सॉर्टेड लिस्ट का मेडियन ढूंढने वाला प्रोग्राम

मान लीजिए हमारे पास दो सॉर्टेड लिस्ट हैं। हमें इन दो लिस्ट का मेडियन ढूंढना है। इसलिए यदि सरणियाँ [1,5,8] और [2,3,6,9] जैसी हैं, तो उत्तर 5 होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

1. एक फंक्शन solve() परिभाषित करें, यह एक सरणी nums1, एक सरणी nums2 लेगा।
2. यदि nums1 का आकार > nums2 का आकार, तो:
   • solve(nums2, nums1) लौटाएँ
3. x := nums1 का आकार, y := nums2 का आकार
4. low := 0, high := x
5. totalLength := x + y
6. जब low <= high, करें:
   • partitionX := low + (high - low) / 2
   • partitionY := (totalLength + 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, तो:
     • यदि totalLength mod 2 0 के समान है, तो:
       • ((maxLeftX और maxLeftY का अधिकतम) + (minRightX और minRightY का न्यूनतम)) / 2 लौटाएँ
     • अन्यथा
       • maxLeftX और maxLeftY का अधिकतम लौटाएँ
   • अन्यथा जब maxLeftX > minRightY, तो:
     • high := partitionX - 1
   • अन्यथा low = partitionX + 1
7. 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));
    return 0;
}

इनपुट

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

आउटपुट

5