ค่ามัธยฐานของอาร์เรย์ที่เรียงลำดับสองรายการใน C++

สมมติว่าเรามีสองอาร์เรย์ อาร์เรย์เหล่านี้จะถูกจัดเรียง เราจึงต้องหาค่ามัธยฐานของอาร์เรย์ทั้งสองนี้ ดังนั้นหากอาร์เรย์เป็นเหมือน [1,5,8] และ [2,3,6,9] คำตอบจะเป็น 5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน findMedianSortedArrays ซึ่งจะใช้อาร์เรย์ nums1 และ nums2

• ถ้าขนาดของ nums1> ขนาดของ nums2 แล้ว

  • เรียกใช้ฟังก์ชัน return findMedianSortedArrays(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 =inf เมื่อ partitionX เป็น x มิฉะนั้น nums1[partitionX]

  • maxLeftY =-inf เมื่อ partitionY เป็น 0 มิฉะนั้น nums2[partitionY-1]

  • maxRightY =inf เมื่อ partitionY เป็น y มิฉะนั้น nums2[partitionY]

  • ถ้า maxLeftX<=minRightY และ maxLeftY <=minRightX แล้ว

    • ถ้า totalLength mod 2 เหมือนกับ 0 แล้ว

      • ผลตอบแทน (สูงสุด maxLeftX และ maxLeftY) + ต่ำสุด minRightX และ minRightY) / 2

    • มิฉะนั้น

      • ส่งคืนค่าสูงสุดของ maxLeftX และ maxLeftY

  • มิฉะนั้นเมื่อ maxLeftX>minRightY แล้ว −

    • สูง :=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