LeetCode: Median of Two Sorted Arrays

题目

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

分析

如果这道题的时间复杂度要求是O(m+n)的话, 就很简单了, 直接merge之后找出中位数即可。 

如果时间复杂度要求为O(log(m+n))的话, 可以把这道题转化为求第k小的问题。

  1. 如果(m+n)是奇数的话, 中位数就是第(m+n)/2+1小; 如果(m+n)是偶数, 中位数就是第(m+n)/2小和第(m+n)/2+1小的平均数。

  2. 然后问题是如何求解第k小的数?

           假设有两个数组:   

           A[0], A[1], ......A[m-1]

           B[0], B[1], ......B[n-1]

           两数组合并后为

           C[0], C[1], ...... C[m+n-1]

           不妨假设m和n都大于k/2, 比较A[k/2-1]和B[k/2-1], 

           如果A[k/2-1] < B[k/2-1], 那么A[k/2-1]及其左侧的元素一定小于合并后的第k小的那个数(即C[k-1])

           为什么?

           可以通过反证来证明, 

           假设A[k/2-1]等于合并后第k小元素 (即C[k-1]), 

           那么实际最多有多少个元素比A[k/2-1]小呢? A[0], A[1]......A[k/2-2]以及B[0], B[1].......B[k/2-2], 共k-2个元素。 也就是说A[k/2-1]最好情况下是第k-1小元素(即C[k-2])

           这与假设矛盾, 因此假设不成立

           因此可以说, A[k/2-1]及其左侧元素一定小于合并后的第k小那个数, 这样就可以排除掉这一范围的数,从而缩小了问题规模。

  1. 再来考虑递归基

           当A为空或者B为空时, 返回B[k-1]或A[k-1]

           当k == 1时, 返回A[0]和B[0]中较小的那个数

           当A[k/2-1] == B[k/2-1]时, 返回A[k/2-1]

           否则的话, 就递归缩小问题规模。

代码

class Solution
{
public:
	double findMedianSortedArrays(int A[], int m, int B[], int n)
	{
		if ((m + n) & 0x01)
			return findKth(A, m, B, n, (m + n) / 2 + 1);
		else
			return (findKth(A, m, B, n, (m + n) / 2) 
					+ findKth(A, m, B, n, (m + n) / 2 + 1)) / 2;
	}

	double findKth(int A[], int m, int B[], int n, int k)
	{
		if (m > n)
			return findKth(B, n, A, m, k);
		else if (m == 0)
			return B[k-1];
		else if (k == 1)
			return min(A[0], B[0]);
		else
		{
			int ALeftCount = min(k / 2, m);
			int BLeftCount = k - ALeftCount;

			if (A[ALeftCount-1] == B[BLeftCount-1])
				return A[ALeftCount-1];
			else if (A[ALeftCount-1] < B[BLeftCount-1])
				return findKth(A+ALeftCount, m-ALeftCount, 
						B, n, k-ALeftCount);
			else//A[ALeftCount-1] > B[BLeftCount-1]]
				return findKth(A, m, 
						B+BLeftCount, n-BLeftCount, k-BLeftCount);
		}
	}
};

参考

http://blog.csdn.net/yutianzuijin/article/details/11499917

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39156991

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();