题目

给定两个有序数组arr1和arr2，已知两个数组的长度分别为m1和m2，求两个数组中的第K小数。要求时间复杂度O(log(m1+ m2))。（题目和解题思路均来自《帅得玩编程》）

举例

eg1. arr1 = [1, 2, 3], arr2 = [3, 4, 5, 6], K = 4.
第K小数为3
eg2. arr1 = [0, 1, 2], arr2 = [3, 4, 5, 7, 8], K = 3.
第K小数为2

分析

该题其实是在两个长度相同的有序数组中找上中位数的扩展。扩展在以下2个方面：

• 长度不同了（一个m1，另一个m2）
• 不再是中位数（第K小数）
  这一题还是用递归解决，那么我们就来看看如何从“原问题”到“子问题”，换句话说，就是如何缩小问题的规模。

原问题—>子问题

在找中位数那题中，利用中位数左右两边元素个数相等的特性，我们通过不断减少数组本身的长度来缩小问题的规模。但由于K的任意性，此法在本题中行不通。但是我们可以通过缩小“K”的值缩小问题的规模。我们以eg1为例讲解：
arr1 = [1, 2, 3]
arr2 = [3, 4, 5, 6]
K = 4
我们令K1 = K / 2（取整除），然后我们分别取出arr1和arr2中第K1小的数arr1[K1 - 1] 和 arr2[K1 - 1]，进行对比，下面分情况讨论：

• arr1[K1 - 1] >= arr2[K1 - 1]，那么目标数肯定不在arr2 的前 K1个数里面。如此一来，我们就要在arr1[…] 和 arr2[K1, …] 里面寻找第K - K1小的数
• arr1[K1 - 1] < arr2[K1 - 1]，同上理

有1个特殊情况，如果数组本身的元素个数小于取整除的结果，那么对于该数组而言，K1 就直接为该数组的长度。

代码

C++代码如下：

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

typedef vector<unsigned short> Vec;
//K从1开始，返回第K大的数
unsigned short ret_kth(const Vec& vec1, const Vec& vec2, int K){
    int len1 = vec1.size(), len2 = vec2.size();
    //空数组情况
    if(len1 == 0 && len2 != 0){
        return vec2[K -1];
    }
    else if(len1 != 0 && len2 == 0){
        return vec1[K - 1];
    }
    else if(K == 1){
        //俩数组均不为空，且需要第1大的数，那么直接返回两数组的最小元素中的较小元素
        return vec1[0] < vec2[0] ? vec1[0] : vec2[0];
    }
    //在K大于1的情况下，先用第K/2大的数排除一部分元素
    int _K = K / 2; //_K < K
    //拿出每个数组的前_K个元素，比较两者中最大的两个数vec1[_K - 1]和vec2[_K - 1]的大小
    //其中较小的那个数及和与其在同一数组中且位于其之前的所有数都不可能为目标数
    //数组1中的第_K大的数，数组2中的第_K大的数
    unsigned short _Kth_1 = _K > len1 ? vec1.back() : vec1[_K - 1];
    int smaller_num1 = _K > len1 ? len1 : _K;  //数组1中可能被排除的元素个数
    unsigned short _Kth_2 = _K > len2 ? vec2.back() : vec2[_K - 1];
    int smaller_num2 = _K > len2 ? len2 : _K; //数组2中可能被排除的元素个数
    if(_Kth_1 <= _Kth_2){
        //排除数组1中的可能元素
        //构造不包含数组1前smaller_num1个元素的子数组
        Vec vec(vec1.begin() + smaller_num1, vec1.end());
        return ret_kth(vec, vec2, K - smaller_num1);
    }
    else{
        //排除数组2中的可能元素
        //....
        Vec vec(vec2.begin() + smaller_num2, vec2.end());
        return ret_kth(vec1, vec, K - smaller_num2);
    }

    return 0;
}
//重载输出流，用于打印数组
ostream& operator<<(ostream& out, const Vec& v){
    for(auto num : v){
        out << num << "  ";
    }
    out << endl;
    return out;
}

// 测试用例
int main(){
    uniform_int_distribution<unsigned short> u(0, 1000);
    default_random_engine e;

    //数组1
    Vec vec1;
    for(int i = 0; i < 10; ++i){
        vec1.push_back(u(e));
    }
    cout << "数组1：";
    sort(vec1.begin(), vec1.end());
    cout << vec1;
    //数组2
    Vec vec2;
    for(int i = 0; i < 0; ++i){
        vec2.push_back(u(e));
    }
    cout << "数组2：";
    sort(vec2.begin(), vec2.end());
    cout << vec2;
    //合并
    cout << "合并之后的数组：";
    Vec joint_vec;
    joint_vec.insert(joint_vec.end(), vec1.begin(), vec1.end());
    joint_vec.insert(joint_vec.end(), vec2.begin(), vec2.end());
    sort(joint_vec.begin(), joint_vec.end());
    cout << joint_vec;
    //返回第K个数
    unsigned short Kth = ret_kth(vec1, vec2, 9);
    cout << Kth << endl;

    return 0;
}