两个排序数组的中位数


难度级别
经常问 土砖 亚马逊 Apple 彭博 ByteDance Facebook 高盛 谷歌 微软 希望
排列 二进制搜索 分而治之

给定两个大小分别为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个位置对数组进行分区还表示该数组中左子集中存在的元素数。

并且我们知道获得的子集的长度应该相等,因此

分区A +分区B =(长度(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分区的左侧有一些元素应放置在Greater(right)子集中。 在这种情况下,我们将i向左移动,j向右移动。

如果B [j-1]> A [i]表示B的分区的左侧有一些元素应放置在Greater(right)子集中。 在这种情况下,我们将j向左移动,i向右移动。

现在要移动分区指针,我们可以使用二进制搜索。

说明

让我们通过一个例子来理解它:

给定两个排序数组A和B。

让我们开始使用二进制搜索对A进行分区,并检查是否可以获得理想的分区。

步骤

左= 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元素才能实现完美分区。

步骤

做left = mid + 1,即left = 4

正确= 6

因此新的中=(4 + 6)/ 2 = 5

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

分区B = 0

A的分区的左侧大于B的分区的右侧。 这意味着我们应该添加更多的元素B以获得完美的分区。

步骤

正确=中期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

如果合并的排序数组的长度为奇数,则答案将只是完美分区左侧的最大值。

使用案列

输入:

输入的第一行包含两个整数n和m,分别表示数组A和B的大小。

下一行包含n个以空格分隔的整数,它们表示A [i],其中0 <= i

下一行包含m个以空格分隔的整数,它们表示B [i],其中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) 因为我们只使用一些变量进行计算。

谢谢阅读!!

參考資料