408-数据结构-中位数

2011统考真题

一个长度为 L(L≥1) 的升序序列 S ，处在第 ⌈L/2⌉ 个位置的数称为 S 的中位数。例如，若序列 S1=⟨11,13,15,17,19⟩ ，则 S1 的中位数是 15 。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列 S2=⟨2,4,6,8,20⟩ ，则 S1 和 S2 的中位数是 11 。现有两个等长的升序序列 A 和 B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：

⑴ 给出算法的基本设计思想。

⑵ 根据设计思想，采用C或C++或Java语言描述，关键之处给出注释。

⑶ 说明你所设计算法的时间复杂度和空间复杂度。

最朴素解法：合并数组c[0:2n-1],返回c[n-1];

• 时间复杂度： O(n) 。
• 空间复杂度： O(n) 。

方法一：双指针

对两个序列从小到大顺序一次访问，当访问到两个序列长度的一半时，为中位数

int findMidNum(vector<int>& s1,vector<int>& s2){
    int len1 = s1.size();
    int len2 = s2.size();
    int m = (len1+len2)>>1;
    int mid_index = (len1+len2)%2 == 0 ? m-1 : m;

    int j = 0,k = 0,min = 0;
    for (int i = 0; i <= mid_index; ++i) {
        if (s1[j] >= s2[k]){
            min = s2[k];
            k++;
        }else{
            min = s1[j];
            j++;
        }
    }
    return min;
}

• 空间复杂度：O(1);
• 时间复杂度：O(n)

方法二：