C++程式：查詢兩個已排序列表的中位數

假設我們有兩個已排序的列表。我們需要找到這兩個列表的中位數。例如，如果陣列為[1,5,8]和[2,3,6,9]，則答案為5。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式solve()，它將接收陣列nums1和陣列nums2作為引數。
  • 如果nums1的大小大於nums2的大小，則
    • 返回solve(nums2, nums1)
  • x := nums1的大小，y := nums2的大小
  • low := 0，high := x
  • totalLength := x + y
  • 當low <= high時，執行以下操作：
    • 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模2等於0，則
        • 返回((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

更新於：2020年11月26日

174 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告