求第K小值&中位数法

题目描述#

给定两个整型数组，长度分别为，且均为单调不下降序列。给定整数，求出第小值。

输入格式#

第一行三个整数，分别表示; 第二行个整数，表示数组; 第二行个整数，表示数组.

输出格式#

一个整数表示第小值.

样例#

4 6 8
1 3 6 7
0 2 4 5 9 11

plaintext

提示#

Sol.1 双指针扫描#

时间复杂度

不赘述

Sol.2 中位数BFPRT#

时间复杂度

BFPRT 求有序数组中位数#

可以通过递归求解计算，时间复杂度

比如，我们有如下长度为(偶数)的两个有序数组：

我们取每个数组中位数进行比较

若,那么，显然中位数不会出现在标黄色区域

那么我们只需要在蓝色区间内查找中位数

此时我们有如下长度为(奇数)的两个有序数组：

若,那么，显然中位数不会出现在标黄色区域

但是当我们去掉不可能的部分后，剩下的部分长度不等

此时我们可以把与比较

若那么可以断定就是中位数

若 ,那么继续递归转到下一次寻找中位数

直到最后每个数组只剩个数，返回其中较小值即可

在本例中，中位数为.

若上述某一步奇偶性或大小表示不同，那么相反操作即可

int dfs(int sa,int ea,int sb,int eb){
    if(sa==ea)return min(a[sa],b[sb]);//终止条件
    int ma=(sa+ea)>>1,mb=(sb+eb)>>1; //数组a,b的中间位置
    bool ji=(ea-sa+1)&1; //判断奇偶
    if(a[ma]>b[mb]){
        if(ji){
            if(b[mb]>=a[ma-1]) return b[mb];
            else return dfs(sa,ma-1,mb+1,eb);
        }else return dfs(sa,ma,mb+1,eb);
    }else{
        if(ji){
            if(a[ma]>=b[mb-1]) return a[ma];
            else return dfs(ma+1,ea,sb,mb-1);
        }else return dfs(ma+1,ea,sb,mb);
    }
}

cpp

利用BFPRT求第K小值#

如给定如下有序数组

长度分别为

对于给定的，分三种讨论

对于第一种，若，我们只需要对进行求中位数即可

即

int solve1(){
    return dfs(1,k,1,k);
}

cpp

对于第二种，若

因为在本例中,我们需要对特判(若则交换)

若,那么就是第小值

若,那么对进行求中位数即可

即

int solve2(){
    if(n<m){
        if(b[k-n]>=a[n]) return b[k-n];
        else return dfs(1,n,k+1-n,k);
    }else{
        if(a[k-m]>=b[m]) return a[k-m];
        else return dfs(k+1-m,k,1,m);
    }
}

cpp

对于第三种，若

我们需要对 $，$ 特判