LeetCode——Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively.

Find the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

有兩個已排序的數組A和B，大小為m 和 n。

找出兩數組的中位數

時間復雜度應該為 O(log (m+n))。

簡單粗暴的方法就是把兩個數組合並成一個數組，排序，取中位數。但是用不到所給的已排序，也體現不了任何算法的意義。時間復雜度：O((m+n)log(m+n))。(不過此方法可以通過。)

	public static double findMedianSortedArrays(int A[], int B[]) {
		int AB[] = new int[A.length + B.length];
		for (int i = 0; i < A.length; i++) {
			AB[i] = A[i];
		}
		for (int i = 0; i < B.length; i++) {
			AB[A.length + i] = B[i];
		}
		Arrays.sort(AB);
		double median = AB.length % 2 == 1 ? AB[AB.length >> 1] : (AB[(AB.length - 1) >> 1] + AB[AB.length >> 1]) / 2.0;
		return median;
	}

	public static double findMedianSortedArrays(int[] a, int[] b) {
		int m = a.length, n = b.length;
		int median = (m + n) / 2;
		if ((m + n) % 2 == 1) // Single median
			return findKthElement(a, b, median);
		else
			// Average of two medians
			return (findKthElement(a, b, median) + findKthElement(a, b,
					median - 1)) / 2.0;
	}

	private static double findKthElement(int[] a, int[] b, int k) {
		int m = a.length, n = b.length;
		int aStart = 0, bStart = 0; // Keep track of the starting index of both
									// arrays under consideration
		int ka, kb;
		while (true) {
			if (aStart == m) // a is empty; find the k-th element in b
				return b[bStart + k];
			if (bStart == n) // b is empty; find the k-th element in a
				return a[aStart + k];
			if (k == 0) // Find the smallest element
				return Math.min(a[aStart], b[bStart]);
			// Set the indices of the elements under consideration
			if (k == 1) { // A special case when k/2-1 < 0
				ka = aStart;
				kb = bStart;
			} else { // Make sure the indices are within the boundaries
				ka = Math.min(m - 1, aStart + k / 2 - 1);
				kb = Math.min(n - 1, bStart + k / 2 - 1);
			}

			// Adjust k and the start index according to the relationship
			// between a[ka] and b[kb]
			if (a[ka] <= b[kb]) { // Any Element in a[aStart...ka] cannot be the one
				k -= ka - aStart + 1;
				aStart = ka + 1;
			} else { // Any Element in b[bStart...kb] cannot be the one
				k -= kb - bStart + 1;
				bStart = kb + 1;
			}
		}
	}