有序顺序表合并求中位数

2011

  1. 寻找序列A和B的中位数
  2. 一个长度为L的升序序列S，处于第[L/2]个位置的数称为S序列的中位数。
  3. 现有两个等长的升序序列A和B，试设计一个在时间和空间复杂度都尽可能高效的算法，找出两个序列A和B的中位数，要求：
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
#include "preset.h"

//顺序表合并（利用三个int类型指针i\j\k）
bool merge(SqList a, SqList b, SqList &c) {
    if (c.length < a.length + b.length) return false;
    int i = 0, j = 0, k = 0;
    //逐个比较 将较小的插入顺序表c中
    while (i < a.length && j < b.length) {
        if (a.elem[i] <= b.elem[j]) {
            c.elem[k] = a.elem[i]; i++; k++;
        } else {
            c.elem[k] = b.elem[j]; j++; k++;
        }
    }
    //剩余元素直接插入结果
    while (i < a.length) {
        c.elem[k] = a.elem[i]; k++; i++;
    }
    while (j < b.length) {
        c.elem[k] = b.elem[j]; k++; j++;
    }
    //修改顺序表c的长度
    c.length = a.length + b.length;
    return true;
}

int main() {
    SqList a = {{11, 13, 15, 17, 19}, 5}; print(a);
    SqList b = {{2, 4, 6, 8, 20}, 5}; print(b);
    SqList c;
    merge(a, b, c); print(c);
    cout << "average : " << c.elem[(c.length - 1)/2];
    return 0;
}