Chương trình tìm giá trị trung bình của hai danh sách đã sắp xếp trong C ++

Giả sử chúng ta có hai danh sách được sắp xếp. Chúng ta phải tìm giá trị trung bình của hai danh sách này. Vì vậy, nếu các mảng giống như [1,5,8] và [2,3,6,9], thì câu trả lời sẽ là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Xác định một hàm giải quyết (), điều này sẽ nhận một mảng nums1, một mảng nums2,
• nếu kích thước của nums1> kích thước của nums2, thì:
  • trả về giải quyết (nums2, nums1)
• x:=kích thước của nums1, y:=kích thước của nums2
• thấp:=0, cao:=x
• totalLength:=x + y
• while low <=high, thực hiện:
  • partitionX:=low + (high - low)
  • phân vùngY:=(totalLength + 1) / 2 - phân vùngX
  • maxLeftX:=(nếu partitionX giống 0 thì -inf, nếu không thì nums1 [partitionX - 1])
  • minRightX:=(nếu partitionX giống với x thì inf, ngược lại là nums1 [partitionX])
  • maxLeftY:=(nếu phân vùngY giống 0 thì -inf, nếu không thì nums2 [phân vùngY - 1])
  • minRightY:=(nếu phân vùngY giống y thì inf, ngược lại là nums2 [phân vùngY])
  • nếu maxLeftX <=minRightY và maxLeftY <=minRightX, thì:
    • nếu totalLength mod 2 giống 0, thì:
      • return ((tối đa maxLeftX và maxLeftY) + (tối thiểu minRightX và minRightY)) / 2
    • Mặt khác
      • trả về tối đa maxLeftX và maxLeftY
  • ngược lại khi maxLeftX> minRightY, thì:
    • cao:=partitionX - 1
  • Nếu không
• trả về 0

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

#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));
}

Đầu vào

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

Đầu ra

5