Median(PAT)

1.题目描述

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.
给定N个整数的递增序列S，中值是中间位置的数。例如，S1={11，12，13，14}的中值为12，S2={9，10，15，16，17}的中值为15。例如，S1和S2的中位数是13。给定两个整数的递增序列，要求找到它们的中值。

2.输入描述:

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 (<=1000000) 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.
每个输入文件包含一个测试用例。每个案例占2行，每一行提供一个序列的信息。对于每个序列，第一个正整数N(<=1000000)是该序列的大小。然后N个整数跟着，用一个空格隔开。保证所有整数都在长int的范围内。

3.输出描述:

For each test case you should output the median of the two given sequences in a line.
对于每个测试用例，您应该在一行中输出两个给定序列的中值。

4.输入例子:

4 11 12 13 14
5 9 10 15 16 17

5.输出例子:

13

6.源代码：

#include<stdio.h>
#include<stdlib.h>
#define MAX 1000000

int main()
{	
	int *num1,*num2,*sort;
	num1=(int *)malloc(MAX * sizeof(int));
	num2=(int *)malloc(MAX * sizeof(int));
	sort=(int *)malloc(2 * MAX * sizeof(int));
	
	int i,j,k,M,N;
	//输入
	scanf("%d", &M);
	for(i = 0; i < M; i++)
		scanf("%d", &num1[i]);

	scanf("%d", &N);
	for(i = 0; i < N; i++)
		scanf("%d", &num2[i]);
	
	i=0,j=0,k=0;
	int mid=(M+N)/2;//中值位置
	//归并两个数组，排成一个有序的数组(参照归并排序)
	while(i < M && j < N && k <= mid)
	{
		if(num1[i] < num2[j])
			sort[k++]=num1[i++];
		else
			sort[k++]=num2[j++];
	}
	while(i < M && k <= mid)
		sort[k++]=num1[i++];
	while(j < N && k <= mid)
		sort[k++]=num2[j++];
	//输出
	if( (M+N)%2 == 0)
		printf("%d", sort[mid-1]);
	else
		printf("%d", sort[mid]);
	return 0;
}