脚本宝典收集整理的这篇文章主要介绍了[Leetcode]4.寻找两个正序数组的中位数，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
关键词：有序，合并，中位数。
中位数表示左右两边数量相等，如果为奇数则为中间的数，如果是偶数就是中间两数求平均。（需要分奇偶讨论） 有序可以减去很多搜索树枝。 合并是个麻烦事，最直接的思路是直接暴力合并，但这样性能很差。或者说能找到两个集合之间的关系，不用合并是最好的。
从特殊点出发寻找一般性规律：
首先对中位数分析：设集合1为s1，长度为m；集合2为s2,长度为n。中位数为p。如果存在P，那么对于合并后的集合肯定是左右两边数量相等。 对于分开的集合，最理想的情况是，p平分集合s1，且p平分s2。此时s1的左集合+s2的左集合=s1的右集合+s2的右集合。由此推导出对于一般情况下的p：设左集合为ls，右集合为rs。若总和为奇数，则ls1+ls2=rs1+rs2+1；若总和为偶数，则ls1+ls2=rs1+rs2。且由于合并后有序，max(ls1,ls2)<=min(rs1,rs2)。由此可以看出s1和s2之间有一定的关系，可以不用合并。
考虑找出两集合之间的关系：
设s1中的遍历指针的index为x，s2中的为y。左集合中包括指针x与y。根据以上推导，假设x，y的位置刚好满足是中位数p的要求。奇数情况下有x+1+y+1=m-1-x+n-1-y+1,化简为y=(m+n-3)/2-x-。偶数情况下有x+1+y+1=m-1-x+n-1-y,化简为y=(m+n-2)/2-x。对所有情况，max(s1[x],s2[y])<=min(s1[x+1],s2[y+1])。所以没必要合并两个集合，两指针之间是有关系的，且最省事方法是二分查找为min(m,n)的集合。
临界值分析：当为m=0 or n=0时，中位数为不为0数组中的中位数。当m=0 and n=0时，无中位数。若m<n。奇数时，当x取最大值m-1时，y=(n-m-1)/2 >=0。x为最小值0时，y=(m+n-3)/2
以上是脚本宝典为你收集整理的[Leetcode]4.寻找两个正序数组的中位数全部内容，希望文章能够帮你解决[Leetcode]4.寻找两个正序数组的中位数所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。