정렬 된 두 배열의 중앙값

난이도 하드
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 ByteDance Facebook 골드만 삭스 구글 Microsoft Wish
배열 이진 검색 분열과 정복조회수 26

각각 크기가 n과 m 인 두 개의 정렬 된 배열 A와 B가 주어집니다. 최종 정렬의 중앙값 찾기 정렬 주어진 두 배열을 병합 한 후 또는 다른 말로하면 정렬 된 두 배열의 중앙값을 찾습니다.

(예상 시간 복잡도 : O (log (n)))

정렬 된 두 배열의 중앙값에 대한 접근 방식 1

두 포인터 방법을 사용하여 A와 B의 병합 정렬 배열을 만듭니다.

그런 다음 해당 배열의 중앙값을 찾으십시오.

정렬 된 두 배열의 중앙값을위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int k=n+m;                   // size of merged sorted array
    int M[k];                   // array which will store integers of A and B in ascending order
    int i=0,j=0,in=0;          // i is a pointer index for A
                              // j is a pointer index for B 
                             // in is a pointer index for M
    while(i<n || j<m){
        if(i<n && j<m){
            if(A[i]<B[j]){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        else{
            if(i<n){
                M[in]=A[i];
                i++;
            }
            else{
                M[in]=B[j];
                j++;
            }
        }
        in++;
    }
    if(k%2==0){
        double m1 = M[k/2];
        double m2 = M[(k/2)-1];
        return (m1+m2)/2;
    }
    else{
        double m1 = M[k/2];
        return m1;
    }
    return -1;    
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
5 5
6 1 2 7 8
3 4 5 6 7
3.5

복잡성 분석

시간 복잡성 : O (max (n, m) 두 배열을 모두 사용하여 병합 정렬 된 배열을 찾기 때문입니다.

공간 복잡성 : O (n + m) 왜냐하면 우리는 O (n + m) 공간 복잡성으로 이어지는 최종 병합 배열을 저장하기 때문입니다.

정렬 된 두 배열의 중앙값에 대한 접근 방식 2

이 문제를 해결하려면 먼저 중앙값이 실제로 무엇을하는지 이해해야합니다.

하나의 서브 세트가 다른 서브 세트보다 크도록 세트를 두 개의 동일한 길이 서브 세트로 분할하는 것입니다.

즉, 한 서브 세트의 모든 요소가 다른 서브 세트의 모든 요소보다 크도록 세트를 두 개의 서브 세트로 분할합니다.

이제 문제로 돌아와서 정렬 된 두 배열의 중앙값을 찾아야합니다.

양쪽 파티션의 왼쪽과 양쪽 파티션의 오른쪽을 더하여 얻은 부분 집합의 길이가 같은 배열 A와 B의 파티션을 찾을 수 있습니까?

정렬 된 두 배열의 중앙값

 

i 번째 위치에서 배열을 분할하는 것은 왼쪽 부분 집합에있는 해당 배열의 요소 수를 나타냅니다.

그리고 얻은 부분 집합의 길이가 같아야한다는 것을 알고 있으므로

partitionA + partitionB = (길이 (A) + 길이 (B) +1) / 2

(최종 병합 정렬 된 배열의 길이가 홀수이면 왼쪽 하위 집합에 더 많은 요소가 포함됩니다)

이제 남은 것은 오른쪽 하위 집합이 왼쪽 하위 집합보다 크도록 주어진 두 배열을 분할하는 방법을 확인하는 것입니다.

정렬 된 배열의 완벽한 파티션을 정의 해 보겠습니다.

배열 A (길이 n)와 배열 B (길이 m)가 있다고 가정 해 보겠습니다.

정렬 된 두 배열의 중앙값

 

우리는 i에서 A와 j에서 B를 분할했습니다.

완벽한 파티션은 다음과 같은 경우입니다.

  • i + j = (n + m + 1) / 2 (부분 집합의 길이가 같음)
  • A [i-1] <= B [j] (i의 왼쪽에있는 A의 요소가 왼쪽 부분 집합에 포함됨)
  • B [j-1] <= A [i] (j의 왼쪽에있는 B의 요소는 왼쪽 부분 집합이됩니다)

A [i-1]> B [j]이면 A의 파티션 왼쪽에 더 큰 (오른쪽) 하위 집합에 배치되어야하는 일부 요소가 있음을 의미합니다. 이 경우 i를 왼쪽으로, j를 오른쪽으로 이동합니다.

B [j-1]> A [i]이면 B의 파티션 왼쪽에 더 큰 (오른쪽) 하위 집합에 배치해야하는 요소가 있다는 의미입니다. 이 경우 j를 왼쪽으로, i를 오른쪽으로 이동합니다.

이제 파티션 포인터를 이동하기 위해 이진 검색을 사용할 수 있습니다.

설명

예를 들어 이해합시다.

두 개의 정렬 된 배열 A와 B가 주어집니다.

바이너리 검색을 사용하여 파티션 A를 시작하고 완벽한 파티션을 얻을 수 있는지 확인하십시오.

단계 1

왼쪽 = 0

오른쪽 = 6

mid = (0 + 6) / 2 = 3 (A의 파티션)

partitionA + partitionB = (length (A) + length (B) +1) / 2를 사용하여 B의 파티션을 얻을 수 있습니다.

partitionB = (6 + 4 + 1) / 2 – partitionA

파티션 B = 5-3 = 2

B의 파티션 왼쪽이 A 파티션의 오른쪽보다 큽니다. 즉, 완벽한 분할을 위해 A의 요소를 더 추가해야합니다.

단계 2

do left = mid + 1 ie, left = 4

오른쪽 = 6

따라서 새로운 중간 = (4 + 6) / 2 = 5

partitionB = (6 + 4 + 1) / 2 – partitionA

파티션B = 0

A의 파티션의 왼쪽이 B의 파티션의 오른쪽보다 큽니다. 이것은 완벽한 분할을 위해 B의 더 많은 요소를 추가해야 함을 의미합니다.

단계 3

옳다 = mid-1

왼쪽 = 4

오른쪽 = 4

따라서 새로운 중간 = (4 + 4) / 2 = 4

partitionB = (6 + 4 + 1) / 2 – partitionA

파티션B = 1

이제 동봉 된 그림에는 총 5 개의 요소가 있고 그 밖에 총 5 개의 요소가 있음을 알 수 있습니다.

또한 A의 파티션 왼쪽은 B의 파티션 오른쪽보다 작습니다.

그리고 B의 파티션의 왼쪽은 A의 파티션의 오른쪽보다 작습니다.

따라서 배열은 다음과 같이 병합됩니다.

배열의 크기가 짝수이므로 최종 정렬 된 배열의 중간 두 요소를 평균하여 중앙값을 얻습니다.

  • 하나는 완벽한 파티션의 왼쪽 최대 값 즉, max (17,11)입니다.
  • 두 번째는 완전 분할의 오른쪽 최소값 즉, min (19,18)입니다.

그렇지 않습니까?

얻은 중앙값 = (17 + 18) / 2

= 17.5

병합 된 정렬 된 배열의 길이가 홀수 인 경우 답은 단순히 완벽한 파티션의 왼쪽 최대 값이됩니다.

입력:

입력의 첫 번째 줄에는 배열 A와 B의 크기를 나타내는 두 개의 정수 n과 m이 포함됩니다.

다음 줄에는 A [i]를 나타내는 n 개의 공백으로 구분 된 정수가 포함됩니다. 여기서 0 <= i

다음 줄에는 B [i]를 나타내는 m 개의 공백으로 구분 된 정수가 포함됩니다. 여기서 0 <= i

출력:

주어진 두 개의 정렬 된 배열의 중앙값을 인쇄합니다.

정렬 된 두 배열의 중앙값을위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;
double findMedian(int A[],int B[],int n,int m){
    int left = 0, right = n;
    while (left <= right) {
        int partitionA = (left + right)/2;
        int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2

        //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
        double maxLeftA = INT_MIN;
        if(partitionA > 0){
            maxLeftA = A[partitionA-1];
        }
            
        //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
        double minRightA = INT_MAX;
        if(partitionA < n){
            minRightA = A[partitionA];
        }
        
        //Similarly for maxLeftB and minrightB
        double maxLeftB = INT_MIN;
        if(partitionB > 0){
            maxLeftB = B[partitionB-1];
        }
            
        double minRightB = INT_MAX;
        if(partitionB < m){
            minRightB = B[partitionB];
        }
        if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
            if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                return (max(maxLeftA, maxLeftB) + min(minRightA, minRightB))/2;
            } 
            else {
                return max(maxLeftA, maxLeftB);
            }
        } 
        else if (maxLeftA > minRightB) {                          //move left side.
            right = partitionA - 1;
        }
        else {                                                   // move right side
            left = partitionA + 1;
        }
    }
    return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
}
int main(){
    int n,m;
    cin>>n>>m;
    int A[n],B[m];
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    for(int i=0;i<m;i++){
        cin>>B[i];
    }
    double median = findMedian(A,B,n,m);
    cout<<median<<"\n";
}
4 5
1 2 7 8
3 4 5 6 7
5

정렬 된 두 배열의 중앙값을위한 JAVA 프로그램

import java.util.Scanner;
public class Main{
    public static double findMedian(int A[], int B[],int n,int m) {
        int left = 0, right = n;
        while (left <= right) {
            int partitionA = (left + right)/2;
            int partitionB = (n + m + 1)/2 - partitionA;      // partitionA + partitionB = (n+m+1)/2
            //if partitionA is 0 then take INT_MIN for maxLeftA (nothing is left in the left of partition)
            double maxLeftA = Integer.MIN_VALUE;
            if(partitionA > 0){
                maxLeftA = A[partitionA-1];
            }
                
            //if partitionA is n then take INT_MAX for minRightA (nothing is left in the right of partition)
            double minRightA = Integer.MAX_VALUE;
            if(partitionA < n){
                minRightA = A[partitionA];
            }
                
            //Similarly for maxLeftB and minrightB
            double maxLeftB = Integer.MIN_VALUE;
            if(partitionB > 0){
                maxLeftB = B[partitionB-1];
            }
                    
            double minRightB = Integer.MAX_VALUE;
            if(partitionB < m){
                minRightB = B[partitionB];
            }
            if (maxLeftA <= minRightB && maxLeftB <= minRightA) {     // check weather it's a perfect partition or not
                if ((n+m) % 2 == 0) {                                // if the sorted merged array is of even length
                    return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB))/2;
                } 
                else {
                    return Math.max(maxLeftA, maxLeftB);
                }
            } 
            else if (maxLeftA > minRightB) {                          //move left side.
                right = partitionA - 1;
            }
            else {                                                   // move right side
                left = partitionA + 1;
            }
        }
        return -1;    // we can't find the median if input is invalid i.e., arrays are not sorted
    }
        
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n,m;
        n = scan.nextInt();
        m = scan.nextInt();
        int A[]=new int[n];
        int B[]=new int[m];
        for(int i=0;i<n;i++){
            A[i] = scan.nextInt();
        }
        for(int i=0;i<m;i++){
            B[i] = scan.nextInt();
        }
        double median = findMedian(A,B,n,m);
        System.out.println(median);  
    }
}
4 6
6 7 8 9
1 2 3 4 5 6
5.5

정렬 된 두 배열의 중앙값에 대한 복잡성 분석

시간 복잡성 : O (log (n))

모든 단계에서와 마찬가지로 검색 공간을 절반으로 줄입니다 (중간 인덱스에서 왼쪽 검색 공간 또는 오른쪽 검색 공간 선택).

공간 복잡성 : O (1) 계산에 몇 가지 변수를 사용하기 때문입니다.

읽어 주셔서 감사합니다!!

참조

Translate »