C++에서 정렬된 두 목록의 중앙값을 찾는 프로그램

<시간/>

두 개의 정렬된 목록이 있다고 가정합니다. 이 두 목록의 중앙값을 찾아야 합니다. 따라서 배열이 [1,5,8] 및 [2,3,6,9]와 같으면 답은 5가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

solve() 함수를 정의하면 배열 nums1, 배열 nums2,
nums1의 크기> nums2의 크기인 경우:
- 반환 풀기(nums2, nums1)
x :=nums1의 크기, y :=nums2의 크기
낮음 :=0, 높음 :=x
총 길이 :=x + y
낮을 때 <=높을 때 다음을 수행합니다.
- partitionX :=낮음 + (높음 - 낮음)
- partitionY :=(totalLength + 1) / 2 - 파티션X
- 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인 경우:
  - 높음 :=파티션X - 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]

C++에서 정렬된 두 목록의 중앙값을 찾는 프로그램

예

입력

출력