C++でソートされた2つの配列の中央値

2つの配列があるとします。これらの配列はソートされています。したがって、これら2つの配列の中央値を見つける必要があります。したがって、配列が[1,5,8]や[2,3,6,9]のような場合、答えは5になります。

これを解決するには、次の手順に従います-

• 関数findMedianSortedArraysを定義します。これには、nums1およびnums2配列が必要です

  。

• nums1のサイズ>nums2のサイズの場合、

  • 関数returnfindMedianSortedArrays（nums2、nums1）

    を呼び出します

• x：=nums1のサイズ、y：=nums2のサイズ

• 低：=0、高：=x

• totalLength：=x + y

• 低<=高、実行-

  • partitionX：=低+（高-低）/ 2

  • partitionY：=（totalLength + 1）/ 2-partitionX

  • maxLeftX =-inf（partitionXが0の場合）、それ以外の場合はnums1 [partitionX-1]

  • maxRightX =partitionXがxの場合はinf、それ以外の場合はnums1 [partitionX]

  • maxLeftY =-inf（partitionYが0の場合）、それ以外の場合はnums2 [partitionY-1]

  • maxRightY =partitionYがyの場合はinf、それ以外の場合はnums2 [partitionY]

  • maxLeftX<=minRightYおよびmaxLeftY<=minRightXの場合、

    • totalLength mod 2が0と同じ場合、

      • return（maxLeftXとmaxLeftYの最大値）+ minRightXとminRightYの最小値）/ 2

    • それ以外の場合

      • maxLeftXとmaxLeftYの最大値を返す

  • それ以外の場合、maxLeftX> minRightYの場合、-

    • high：=partitionX-1

  • それ以外の場合は低い：=partitionX + 1

• 0を返す

例（C ++）

理解を深めるために、次の実装を見てみましょう-

#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[partitionX1] );
         int minRightX = (partitionX == x?INT_MAX :
         nums1[partitionX]);
         int maxLeftY = (partitionY ==0?INT_MIN:nums2[partitionY1] );
         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));
}

入力

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

出力

5