4.寻找两个正序数组的中位数

困难题

这题做着还是感觉挺有典型性的。从一个比较菜的选手角度入手，我将展示一些思考方向，包括错误和正确的，来合理地得到符合题目的解答。
首先，我们当然想是偷懒，将两个数组合并再调用系统函数直接sort，取中位数。但是题目不允许，因为复杂度太高。稍微思考一下，两个数组合并就得一个数一个数比大小，复杂度必然是O(m+n)等级的。由此我们不难发现，只要是需要一个数一个数往后逐个对比的算法，复杂度要求必然都是达不到的。如何才能使得复杂度中出现log？自然第一想到就是二分，树，递归这一类的概念。而题目中又给出数组已经排序好的条件，二分法就一定是一个选择了。
接下来需要搞明白我们的目标是什么。我们只要找到中位数就可以了，不关心这个数的具体位置。中位数是中间的数，就是从前往后数，排在中间的数，也就是第k小的数（k=数组长度/2）。于是，我们将所求问题转化为寻找两个有序数组中第k小的数。这里是一个思考点，因为需要转化目标。
我们用二分法递归来寻找第k小的数。注意：二分法的二分是针对k的二分，不是数组长度的二分，因为在递归中k是会变的。先不考虑边界情况，考虑一下最一般的情况：

假设在两个正序数组中寻找第7小的数。将两个数组以7/2二分，得到A前（1,3,4），A后（9），B前（1,2,3），B后（4,5,6,7,8,9,10）四个部分。本次二分目标是筛选出7/2=3个数，这些数不一定要是当前这两个数组中最小的数，只要满足是“前7小的”即可。能够保证这一条件的理由如下：比较图中指针位置的数，B前（1,2,3）中的3小于A前（1,3,4）中的4。即使A前（1,3,4）中其余的数都小于中位数，也只有k/2-1=2个，加上B前（1,2,3）的k/2个共k-1=5个，不会超过k小。将这筛选出的3个数排除，组成的两个新数组可以进行类似递归运算，需要调整的是数组和k的大小。
我们假设这两个数组一开始都很长，然后一点点被排除。递归到后面的结果需要考虑的边界情况是：

1. 某个数组中的数太少了，不满k/2个
2. 某个数组中所有的数都被排除，现在为空数组

结合代码，详细分类讨论一下寻找第k小函数的写法。

#include 
#include 

using namespace std;


class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int k = (m+n)/2+1; //下面寻找第k小的数。如果m+n有奇数个，找第k小的数两次，取平均数；如果m+n有偶数个，找第k小和第k+1小的数，取平均数
        int left = (m+n+1)/2;
        int right = (m+n+2)/2; //表示中间的两个数。屏蔽了偶数和奇数的区别
        return (getKth(nums1,nums2,0,m-1,0,n-1,left)+getKth(nums1,nums2,0,m-1,0,n-1,right))*0.5;
         
    }

    //使用二分法寻找第k小的数。每次需要砍掉前k/2个数，直到k=1
    double getKth(vector<int>& nums1, vector<int>& nums2, int ahead, int aend, int bhead, int bend, int k){

        //递归结束情况
        if(k == 1){
            if(ahead > aend){
                //cout<
                return nums2[bhead];
            } 
               
            else if(bhead > bend) {
                //cout<
                return nums1[ahead];
            }
            else {
                //cout<
                return min(nums1[ahead],nums2[bhead]);
            }
        }

        int mid = k/2; //本轮计划干掉mid个数，虽然可能会不满

        if((aend - ahead + 1 >= mid) && (bend - bhead + 1 >= mid)){
            //两个数组都够
            if(nums1[ahead+mid-1] < nums2[bhead+mid-1]) return getKth(nums1,nums2,ahead+mid,aend,bhead,bend,k-mid);
            else return getKth(nums1,nums2,ahead,aend,bhead+mid,bend,k-mid);
        }

        if((ahead <= aend) && (bhead <= bend)){
            if(aend - ahead + 1 < mid){
                //a不够，b够，且都不为零
                if(nums1[aend] < nums2[bhead+mid-1]) return getKth(nums1,nums2,aend+1,aend,bhead,bend,k-(aend-ahead+1));
                else return getKth(nums1,nums2,ahead,aend,bhead+mid,bend,k-mid);
            }
            if(bend - bhead + 1 < mid){
                //a够，b不够，且都不为零
                if(nums1[ahead+mid-1] < nums2[bend]) return getKth(nums1,nums2,ahead+mid,aend,bhead,bend,k-mid);
                else return getKth(nums1,nums2,ahead,aend,bend+1,bend,k-(bend-bhead+1));
            }
            else return -100000.0;
        }

        if(ahead > aend){
            //a为零
            return getKth(nums1,nums2,ahead,aend,bhead+mid,bend,k-mid);
        }

        if(bhead > bend){
            //b为零
            return getKth(nums1,nums2,ahead+mid,aend,bhead,bend,k-mid);
        }
        
        //不可能都不够，但是不写一个编译器有报错，乱写一个
        //其实可以通过更好的逻辑控制省去这个，现在这种写法不推荐，所以写了一个很臭的数字，希望能下次改正
        else return -114514;
    }

};


int main() {
    vector<int> nums1({1});
    vector<int> nums2({1,2,3,4,5,6,7,8,9,10});
    Solution st;

    
    cout<<st.findMedianSortedArrays(nums1,nums2)<<endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

对部分代码进行解释：

• 使用left和right将求中位数的奇数偶数不同情况在代码形式上统一了，虽然对奇数情况会多求一次。
• k=1时，找第1小的数只要比较数组开头的数，作为结束递归的条件。
• 标记数组开头的ahead和bhead指针只会增大。当增大到比aend，bend还大的时候数组就为空。
• 数组中元素不足k/2，则一最后一个数为此数组基准。
• 数组中无元素，则直接筛除另一个数组中k/2个数。
• 可以省去一些代码语句来对情况进行合并。但是我认为，这对复杂的影响不大，而且代码是给人看的，条理越清晰越好，所以我基本上都是用if语句单独分开来写。