Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 정렬된 두 배열의 중앙값


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

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

  • findMedianSortedArrays 함수를 정의합니다. 이것은 nums1 및 nums2 배열을 사용합니다.

  • nums1의 크기> nums2의 크기인 경우

    • findMedianSortedArrays(nums2, nums1)

      반환 함수 호출
  • x :=nums1의 크기, y :=nums2의 크기

  • 낮음 :=0, 높음 :=x

  • 총길이 :=x + y

  • 낮음<=높은 동안 −

    • partitionX :=낮음 + (높음 - 낮음) / 2

    • 파티션Y :=(총길이 + 1) / 2 - 파티션X

    • 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과 같으면

        • 반환(maxLeftX 및 maxLeftY의 최대값) + minRightX 및 minRightY의 최소값) / 2

      • 그렇지 않으면

        • maxLeftX 및 maxLeftY의 최대값 반환

    • 그렇지 않으면 maxLeftX>minRightY일 때 -

      • 높음 :=파티션X - 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