学步园

问题：

给定两个有序数组a，b，长度都为n，求解两个有序数组中第K大的数。

分析：

对于所有的这种问题，我们首先想到缩减问题的规模，但是缩减后，求解对象依旧不变，保持一致性，我们首先找到彼此的中位数，判断中位数之间的大小，设a的中位数为x，b的中位数为y，如果x+y>k，那么所有b中的y和大于y的数都大于k，删除不影响问题规模；如果x+y<k，那么删除a中x和x之前的数字，并且将k减小到k-x，在剩余中查找第k-x大的数字，递归查找下去。

代码如下：

/*
 * findMedian.cpp
 *
 *  Created on: 2012-10-28
 *      Author: happier
 */
#include <stdio.h>
#include <stdlib.h>
#define N 5

int a[N] =
{ 1, 2, 3, 4, 5 };
int b[N] =
{ 4, 5, 6, 7, 8 };

//获取数组a中从s1到n1个元素
//数组b中s2到n2个元素，合并后的第k大元素
int getMedian(int s1, int n1, int s2, int n2, int k)
{
	//x和y分别记录中间值的索引
	int x, y;

	x = (s1 + n1) / 2; //记录a的中位数索引
	y = (s2 + n2) / 2; //记录b的中位数索引

	if (s1 > n1)
		return b[s2 + k - 1];
	if (s2 > n2)
		return a[s1 + k - 1];

	if (a[x] <= b[y])
	{
		if (k <= (x - s1) + (y - s2) + 1)
		{
			return getMedian(s1, n1, s2, y - 1, k);
		}
		else
		{
			return getMedian(x + 1, n1, s2, n2, k - (x - s1) - 1);
		}
	}
	else
	{
		if (k <= (x - s1) + (y - s2) + 1)
		{
			return getMedian(s1, x - 1, s2, n2, k);
		}
		else
		{
			return getMedian(s1, n1, y + 1, n2, k - (y - s2) - 1);
		}
	}

	return 0;
}

int main()
{
	int i;
	i = getMedian(0, 4, 0, 4, 8);
	printf("%d\n", i);
	return 0;
}

代码转自网友

总结：

问题规模减小，但是注意修改子问题。