题目描述

题目中位数定义：处在第 ⌈L/2⌉个位置的数称为 S的中位数。
由于是两个等长且为n的递增序列，所以中位数必然是合并之后的第n个数
所以不难想到可以利用归并排序的归并过程，归并到第n个数时，即为中位数

样例

输入：S1 = [11, 13, 15, 17, 19], S2 = [2, 4, 6, 8, 20]

输出：11

时间复杂度O(n)

C++ 代码

class Solution {
public:
    int medianSearch(vector<int>& S1 , vector<int>& S2) {
        int cnt = 0, i = 0, j = 0, n = S1.size();
        while(i < n && j < n)
        {
            if(S1[i] < S2[j])
            {
                i ++;
                cnt ++;
                if(cnt == n) return S1[i - 1];
            }else
            {
                j ++;
                cnt ++;
                if(cnt == n) return S2[j - 1];
            }
        }
    }
};