Trung vị của hai mảng đã sắp xếp trong C++

Giả sử ta có hai mảng đã sắp xếp. Ta phải tìm trung vị của hai mảng này. Ví dụ: mảng [1,5,8] và [2,3,6,9], kết quả = 5.

Để giải quyết, ta làm theo các bước:

• Định nghĩa hàm findMedianSortedArrays nhận nums1, nums2.
• Nếu kích thước nums1 > nums2: gọi lại findMedianSortedArrays(nums2, nums1).
• x := kích thước nums1, y := kích thước nums2.
• low := 0, high := x.
• totalLength := x + y.
• while low <= high:
  • partitionX := low + (high - low) / 2.
  • partitionY := (totalLength + 1) / 2 - partitionX.
  • maxLeftX = -inf nếu partitionX==0, ngược lại nums1[partitionX-1].
  • minRightX = inf nếu partitionX==x, ngược lại nums1[partitionX].
  • maxLeftY = -inf nếu partitionY==0, ngược lại nums2[partitionY-1].
  • minRightY = inf nếu partitionY==y, ngược lại nums2[partitionY].
  • Nếu maxLeftX <= minRightY VÀ maxLeftY <= minRightX:
    • Nếu totalLength chẵn: trả về (max(maxLeftX,maxLeftY) + min(minRightX,minRightY)) / 2.
    • Ngược lại: trả về max(maxLeftX, maxLeftY).
  • Ngược lại nếu maxLeftX > minRightY: high = partitionX - 1.
  • Ngược lại: low = partitionX + 1.
• Trả về 0.

Ví dụ (C++)

Xem triển khai dưới đây:

#include <bits/stdc++.h> using namespace std; class Solution { public:    double findMedianSortedArrays(vector& nums1, vector<int>& nums2) {       if(nums1.size()>nums2.size())          return findMedianSortedArrays(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<int> v1 = {1,5,8}, v2 = {2,3,6,9};    cout << (ob.findMedianSortedArrays(v1, v2)); }

Đầu vào

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

Đầu ra

5