C++ में दो क्रमबद्ध सूचियों का माध्यिका ज्ञात करने का कार्यक्रम

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

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

• एक फ़ंक्शन को हल करें परिभाषित करें (), यह एक सरणी संख्या 1, एक सरणी संख्या 2 लेगा,
• यदि nums1 का आकार> nums2 का आकार, तो:
  • रिटर्न सॉल्व(nums2, nums1)
• x :=nums1 का आकार, y :=nums2 का आकार
• निम्न:=0, उच्च:=x
• कुल लंबाई :=x + y
• कम <=उच्च होने पर, करें:
  • विभाजनX :=निम्न + (उच्च-निम्न)
  • विभाजनY :=(कुल लंबाई + 1) / 2 - विभाजनX
  • maxLeftX :=(यदि पार्टीशनX 0 के समान है, तो -inf, अन्यथा nums1[partitionX - 1])
  • minRightX :=(यदि पार्टीशनX, x के समान है, तो inf, अन्यथा nums1[partitionX])
  • maxLeftY :=(यदि पार्टीशनवाई 0 के समान है, तो -इनफ, अन्यथा nums2[partitionY - 1])
  • minRightY :=(यदि पार्टीशन वाई, y के समान है, तो inf, अन्यथा nums2[partitionY])
  • यदि maxLeftX <=minRightY और maxLeftY <=minRightX, तो:
    • यदि टोटल लेंथ मोड 2 0 के समान है, तो:
      • वापसी ((अधिकतम maxLeftX और maxLeftY) + (न्यूनतम minRightX और minRightY))/2
    • अन्यथा
      • अधिकतम maxLeftX और maxLeftY लौटाएं
  • अन्यथा जब maxLeftX> minRightY, तब:
    • उच्च:=विभाजनX - 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