PAT 1029 Median (25分) 有序数组合并

题目

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input Specification: Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤2×10​5) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification: For each test case you should output the median of the two given sequences in a line.

Sample Input: 4 11 12 13 14 5 9 10 15 16 17 Sample Output: 13

题目解读

首先，给出递增序列中位数的定义，奇数个元素不用多说，就是最中间那个；对于偶数个元素，比如 1 2 3 4，定义2是中位数（平常可能会（2+3）/ 2，这里不是）。

两行输入，每一行第一个数字n是序列个数，后面是n个数字的递增序列。 要求输出这两个递增序列合并后的序列的中位数。

补：虽然题目说数组元素范围不超过long int，但其实我试了一下用int就可以了。

思路解析

• 关于两个递增序列合并的问题我就不多说了，无非就是每次比较两个序列当前元素，选择较小的那个放入新的序列，然后被选取的那个序列的指针和最后得到的序列的指针顺序后移一位。大体框架是这样的：

	while (i < n && j < m) {
		c[k++] = a[i] < b[j] ? a[i++] : b[j++];
	}
	if (i < n) {
		while (i < n) {
			c[k++] = a[i++];
		}
	} else if (j < m) {
		while (j < m) {
			c[k++] = b[j++];
		}
	}

• 然后就是中位数的选择问题，一共有 n + m 个元素，最中间的那个就是第 （n + m + 1）/ 2个数字，为什么要加1，比如 1 2 3 4 5 6 7，7 / 2 = 3，但是4是中位数，4是第四个元素，当然你如果要按下标来说的话，4的下标的确是3，不用加1再除以2.
• 第一种思路就是创建第三个数组c[a.size()+b.size()]，按照我上面写的代码把a[]和b[]顺序合并到c中，然后输出c的中位数（c[(m+n)/2]）。但是这种方式提交后最后一个测试点是运行超时，其实是内存溢出了。
• 我们考虑一下，首先，假如第mid个数字是c[]的中位数，那么我们是不需要c[]中mid之后的写那些数字，那么我们在合并a和b的时候，记录一下当前合并了几个数字，当合并到第mid个数时就退出while；那么关于mid前面的那些元素我们也是不需要保存的，我们只需要一个变量，每次它都被赋值为a[]和b[]中当前最小的那个，当合并到第mid次时，这个变量就是我们需要的中位数。

	while (i < n && j < m) {
        // 每次找a和b当前位置小的那个那个元素
        res = a[i] < b[j] ? a[i++] : b[j++];
        // 得到了mid个就退出
        if (++cnt == mid) break;
    }

• 这里有两个问题：第一个是这个mid的取值，还记得我们上面那个1234567的例子吗，我们这里是按照当前统计到第几个数字了来记录的，中位数是第4个，所以 mid =（n+m+1）/2; 第二个问题是：如果a和b中一个特别短呢？比如 a[] : 2，b[] : 1 3 5 7。这样的话while退出就可能是a和b中某个数组合并完了，但是还没达到第mid个，就拿这个例子来说，到while退出时，我们应该是先选择1，再选择2，然后a合并完了，while退出了，但此时我们的cnt只记录到2，所以我们还差mid-cnt个数字，所以我们应该去b里面继续向后推进mid-cnt个位置，得到中位数。

	// while退出后
	if (cnt < mid) {
        // b[]数组全部元素合并过了不够mid个，已经得到了cnt个，还差 mid - cnt个
        // 应该在a[]第i个的基础上向后移mid - cnt个位置，但是 【第几个】 和 【下标】 之间是差了个1的。
        if (i < n) 
            res = a[i + mid - cnt - 1];
        else
            res = b[j + mid - cnt - 1];
    }

注意事项（重点）

• 不要用三个数组，a[200000]，b[200000]，c[400000]，会内存溢出。
• 注意数组【第几个】元素与【下标】之间是差了个1的，实在不知道要不要加1或减1就写个例子试一下。
• 不要用cin输入，亲测，最后一个测试点依然是运行超时。

最终代码

#include <iostream>
using namespace std;

// 定义三个数组会溢出
// 用cin会溢出
int main() {

    int n, m, i, j, res, cnt, mid, a[200000], b[200000];
    // 第一组有n个数
    // cin >> n;
    scanf("%d", &n);
    // for (i = 0; i < n; ++i) cin >> a[i];
    for (i = 0; i < n; ++i) scanf("%d", &a[i]);
    // cin >> m;
    scanf("%d", &m);
    // 第二组有m个数
    // for (j = 0; j < m; ++j) cin >> b[j];
    for (j = 0; j < m; ++j) scanf("%d", &a[j]);
    // 合起来的一半有  假如 7 个 1 2 3 4 5 6 7，中位数是4，第4个数字
    mid = (n + m + 1) / 2;
    // cnt 得到第几个数
    i = 0; j = 0, cnt = 0;
    while (i < n && j < m) {
        // 每次找a和b当前位置小的那个那个元素
        res = a[i] < b[j] ? a[i++] : b[j++];
        // 得到了mid个就退出
        if (++cnt == mid) break;
    }
    // 判断退出条件
    if (cnt < mid) {
        // b[]数组全部元素合并过了不够mid个，已经得到了cnt个，还差 mid - cnt个
        // 应该在a[]第i个的基础上向后移mid - cnt个位置，但是 【第几个】 和 【下标】 之间是差了个1的。
        if (i < n) 
            res = a[i + mid - cnt - 1];
        else
            res = b[j + mid - cnt - 1];
    }
    cout << res;
    return 0;
}