C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で2つの並べ替えられたリストの中央値を見つけるプログラム


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

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

  • 関数solve()を定義します。これには、配列nums1、配列nums2が必要です。
  • nums1のサイズ>nums2のサイズの場合:
    • returnsolve(nums2、nums1)
  • x:=nums1のサイズ、y:=nums2のサイズ
  • 低:=0、高:=x
  • totalLength:=x + y
  • 低い<=高い間、次のことを行います:
    • partitionX:=low +(high-low)
    • 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と同じ場合、次のようになります。
        • return((maxLeftXとmaxLeftYの最大値)+(minRightXとminRightYの最小値))/ 2
      • それ以外の場合
        • maxLeftXとmaxLeftYの最大値を返します
    • それ以外の場合、maxLeftX> minRightYの場合、次のようになります。
      • high:=partitionX-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

  1. グラフ内の2つのノード間のパスを見つけるC++プログラム

    このプログラムでは、特定のグラフでDFSを使用して、2つのノード間にパスが存在するかどうかを確認できます。 アルゴリズム Begin    function isReach() is a recursive function to check whether d is reachable to s :    A) Mark all the vertices as unvisited.    B) Mark the current node as visited and enqueue it and it will be used to

  2. 二分探索アプローチを使用して2つのソートされた配列の中央値を見つけるC++プログラム

    二分探索アプローチを使用して、2つのソートされた配列の中央値を見つけるC++プログラムを開発します。 アルゴリズム Begin    Function median() with both the arrays and the start and end indexes of each array, which have two arrays and their respective elements as argument.       A) first calculate the array length as e1 - s1, here