XNUMXつのソートされた配列の中央値


難易度 ハード
よく聞かれる Adobe Amazon (アマゾン) Apple ブルームバーグ ByteDance Facebook ゴールドマン·サックス Google マイクロソフト ウィッシュ
配列 バイナリ検索 分割統治

それぞれサイズnとmのXNUMXつのソートされた配列AとBが与えられます。 ソートされた最終的な中央値を見つける 配列 与えられたXNUMXつの配列をマージした後に得られる、言い換えれば、XNUMXつのソートされた配列の中央値を見つけると言います。

(予想される時間計算量:O(log(n)))

1つのソートされた配列の中央値に対するアプローチXNUMX

XNUMXポインター法を使用して、AとBのマージされたソート済み配列を作成します。

次に、その配列の中央値を見つけるだけです。

XNUMXつのソートされた配列の中央値のための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つのソートされた配列の中央値に対するアプローチXNUMX

この問題を解決するには、最初に中央値が実際に何をするのかを理解する必要があります。

これは、XNUMXつのサブセットが他のサブセットよりも大きくなるように、セットをXNUMXつの等しい長さのサブセットに分割することです。

つまり、XNUMXつのサブセットのすべての要素が他のサブセットのすべての要素よりも大きくなるように、セットをXNUMXつのサブセットに分割します。

ここで問題に戻り、XNUMXつのソートされた配列の中央値を見つける必要があります。

両方のパーティションの左側と両方のパーティションの右側を追加して得られるサブセットの長さが等しくなるように、配列AとBのパーティションを見つけることができますか?

XNUMXつのソートされた配列の中央値

 

配列をi番目の位置で分割することは、左側のサブセットに存在するその配列の要素の数も示します。

そして、得られるサブセットの長さは等しくなければならないことがわかっているので、したがって

パーティションA +パーティションB =(長さ(A)+長さ(B)+1)/ 2

(最終的にマージされたソート済み配列の長さが奇数の場合、左側のサブセットにはより多くの要素が含まれます)

残っているのは、右側のサブセットが左側のサブセットよりも大きくなるように、指定されたXNUMXつの配列を分割する方法を確認することだけです。

ソートされた配列の完全なパーティションを定義しましょう。

配列A(長さn)と配列B(長さm)があるとしましょう

XNUMXつのソートされた配列の中央値

 

Aをiに、Bをjに分割しました。

完璧なパーティションは次の場合です。

  • 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を右に移動します。

ここで、パーティションポインターを移動するために、バイナリ検索を使用できます。

説明

例を挙げて理解しましょう。

XNUMXつのソートされた配列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 –パーティションA

パーティションB = 5-3 = 2

Bのパーティションの左側がAのパーティションの右側よりも大きい。 これは、完全なパーティションを作成するには、Aの要素をさらに追加する必要があることを意味します。

ステップ2

left = mid + 1、つまりleft = 4を実行します

右= 6

したがって、新しいmid =(4 + 6)/ 2 = 5

partitionB =(6 + 4 + 1)/ 2 –パーティションA

パーティションB = 0

Aのパーティションの左側がBのパーティションの右側よりも大きいため。 これは、完全なパーティションを取得するには、Bの要素をさらに追加する必要があることを意味します。

ステップ3

右に行う= mid-1

左= 4

右= 4

したがって、新しいmid =(4 + 4)/ 2 = 4

partitionB =(6 + 4 + 1)/ 2 –パーティションA

パーティションB = 1

これで、同封の図に合計5つの要素があり、その外側に合計5つの要素があることがわかります。

また、Aのパーティションの左側はBのパーティションの右側よりも小さくなっています。

また、Bのパーティションの左側は、Aのパーティションの右側よりも小さくなっています。

したがって、配列は次のようにマージされます。

配列のサイズが同じであるため、中央値は、最終的にソートされた配列の中央のXNUMXつの要素の平均を取ることによって取得されます。

  • 17,11つは、完全なパーティションの左側の最大値、つまりmax(XNUMX)になります。
  • 19,18番目は、完全なパーティションの右側の最小値、つまりmin(XNUMX)になります。

そうじゃない?

得られた中央値=(17 + 18)/ 2

= 17.5

マージされたソート済み配列の長さが奇数の場合、答えは単純に完全なパーティションの左側の最大値になります。

入力:

入力の最初の行には、配列AとBのサイズを示すXNUMXつの整数nとmが含まれています。

次の行には、A [i]を表すn個のスペースで区切られた整数が含まれています。ここで0 <= i

次の行には、B [i]を表すm個のスペースで区切られた整数が含まれています。ここで0 <= i

出力:

指定されたXNUMXつのソートされた配列の中央値を出力します。

XNUMXつのソートされた配列の中央値のための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

XNUMXつのソートされた配列の中央値のための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

XNUMXつのソートされた配列の中央値の複雑さの分析

時間計算量:O(log(n))

すべてのステップと同様に、検索スペースを半分に減らしています(中央のインデックスから左の検索スペースまたは右の検索スペースを選択します)。

スペースの複雑さ:O(1) 計算にいくつかの変数を使用するだけだからです。

読んでくれてありがとう!!

リファレンス