找出两个已经排好序的数组的中位数 [No. 16]

问题：

给两个已经排好序的数组，一个长度为 m (m >= 1), 一个长度为 n (n >= 1)，找出这两个数组的中位数。时间复杂度要求为 O(m+n), 空间复杂度为 O(1)。

其实这个问题本身来讲是不难的，关键的关键，是对一些边界条件的处理。

思路：

我们首先判断中位数的位置，如果 m+n 为奇数，那么中位数的位置是 第 (m+n+1)/2。 如果 m + n 为偶数，那么我们要找出第 (m+n)/2 和 第(m+n)/2 + 1, 然后求平均。

我们在两个数组上都分配一个“指针”指到起始位（假定A数组的指针为pa, B数组的指针为pb），然后根据它们值的大小，指针不断的向前推进，直到总的被遍历的数的个数为(m+n+1)/2 （奇数情况）或者为(m+n)/2 （偶数情况）。

我们在移动指针对数组中的数进行比较的时候，我们要考虑指针是否已经超过数组的大小，然后才能进行比较，这是一个非常值得注意的地方。

public class Median {
	
	public static float median(int[] a, int[] b) {
		if (a == null || b == null || a.length == 0 || b.length ==0) return 0;
		int lengthA = a.length;
		int lengthB = b.length;
		
		boolean even = (lengthA + lengthB) % 2 == 0 ? true : false;
		int index = -1;
		int pa = 0;
		int pb = 0;
		float median1 = 0;
		
		if (even == true) {
			if (lengthA + lengthB == 2) return (float) (a[0] + b[0]) / 2;
			while (index != (lengthA + lengthB)/2 - 1) {
				if (pa < lengthA && pb < lengthB) {
					if (a[pa] < b[pb]) {
						median1 = a[pa];
						pa++;
					} else {
						median1 = a[pb];
						pb++;
					}
				} else if (pa == lengthA) {
					median1 = b[pb];
					pb++;
				} else {
					median1 = a[pa];
					pa++;
				}
				index++;
			}

			if (pa > lengthA - 1) {
				return (float)(median1 + b[pb]) / 2;
			} else if (pb > lengthB - 1) {
				return (float)(median1 + a[pa]) / 2;
			} else {
				int median2 = (a[pa] < b[pb]) ? a[pa] : b[pb];
				return (float)(median1 + median2) / 2;
			}
			
		} else {
			while (index != (lengthA + lengthB)/2) {
				if (pa < lengthA && pb < lengthB) {
					if (a[pa] < b[pb]) {
						median1 = a[pointerA];
						pointerA++;
					} else {
						median1 = b[pb];
						pb++;
					}
				} else if (pa == lengthA) {
					median1 = b[pb];
					pb++;
				} else {
					median1 = a[pa];
					pa++;
				}
				index++;
			}	
		
		}	
		return median1;
	}
	
	public static void main(String[] args) {
		
		int[] b = {1, 2, 3, 4};
		int[] a = {5, 6, 7, 8,9,10};
		System.out.println(median(a,b));
	}
}