Java怎么寻找两个有序数组的中位数
这篇文章主要介绍"Java怎么寻找两个有序数组的中位数"，在日常操作中，相信很多人在Java怎么寻找两个有序数组的中位数问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"Java怎么寻找两个有序数组的中位数"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
There are two sorted arrays nums1 and nums2 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)).
Example 1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
1.自己的想法是 一共m + n 个，我们可以新建一个List 然后每把最小的数放进去，代码如下：
class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ leng = len(nums1) + len(nums2) tmpLen = leng//2 + 1 newList = [0]*tmpLen i = 0 j = 0 for k in range(tmpLen): if i == len(nums1): newList[k] = nums2[j] j += 1 elif j == len(nums2): newList[k] = nums1[i] i += 1 else: if nums1[i] < nums2[j]: newList[k] = nums1[i] i += 1 else: newList[k] = nums2[j] j += 1 if leng %2 == 0: return (newList[tmpLen - 2] + newList[tmpLen - 1])/2 else: return newList[tmpLen - 1]
2.类似与折半查找的思路，
由于题目要求的时间复杂度是（log（m+n))，如果我们直接把两个数组整合一起，那么时间复杂度肯定超过（log（m+n））。所以整理肯定是不行的。那么还有什么方法吗？答案是肯定的。
首先我们要先了解中位数的概念，中位数就是有序数组的中间那个数。那么如果我们将比中位数小的数和比中位数大的数去掉同样的个数，中位数的值也不会变化（数组的个数为偶数的时候另外讨论，因为那时候中位数是中间两个数的平均值，所以中位数旁边两个数不能去掉）。
所以我们不妨试着将数组长度不断缩短。这里不妨提出一个引理。假设有两个有序数组am，bn，他们整合后的有序数组为cn+m。他们的中位数分别是Am/2,Bn/2,C(m+n)/2。如果Am/2 < Bn/2,则 A0…m/2 <= C(m+n)/2 <= Bn/2…n 。
引理证明：
假设 Am/2 > C(m+n)/2 ，那么 Bn/2 > C(m+n)/2，所以在数组Am里有大于m/2个数大于C(m+n)/2，在数组Bn里也有n/2个数大于C(m+n)/2
也就是说在Cn+m里有（m+n）/2个数大于C(m+n)/2，此时就C(m+n)/2不再是数组Cn+m的中位数。
所以A0…m/2 <= C(m+n)/2。
同理可得C(m+n)/2 <= Cn/2…n 。
根据上述引理，我们不妨设m>n，那么我们根据判断两个数组的中位数大小，每个数组每次减少n/2长度，直到n为1。如此，我们通过减少log（n）次可以得到答案。这种方法的时间复杂度是（log（min（m,n）））。
class Solution: def getMedian(self,nums): size = len(nums) if size == 0: return [0,0] if size % 2 == 1: return [nums[size//2],size//2] else: return [(nums[size//2 - 1] + nums[size//2])/2,size//2] def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ size1 = len(nums1) # ig longer size2 = len(nums2) if size1 < size2: return self.findMedianSortedArrays(nums2,nums1) m1 = self.getMedian(nums1) m2 = self.getMedian(nums2) if size2 == 0: return m1[0] if size2 == 1: if size1 == 1: return (m1[0] + m2[0])/2 if size1 % 2 == 0: if nums2[0] < nums1[size1//2 - 1]: return nums1[size1//2 -1] if nums2[0] > nums1[size1//2]: return nums1[size1//2] else: return nums2[0] else: if nums2[0] < nums1[size1//2 - 1]: return (nums1[size1//2 - 1] + nums1[size1//2])/2 if nums2[0] > nums1[size1//2 + 1]: return (nums1[size1//2 + 1] + nums1[size1//2])/2 else: return (nums2[0] + nums1[size1//2])/2 if size1 % 2 == 0: if size2 % 2 == 0: if nums1[size1//2 - 1] > nums2[size2//2 - 1] and nums2[size2//2] > nums1[size1//2]: return m1[0] if nums1[size1//2 - 1] < nums2[size2//2 - 1] and nums2[size2//2] < nums1[size1//2]: return m2[0] if m1[0] < m2[0]: return self.findMedianSortedArrays(nums1[m2[1]:],nums2[:size2 - m2[1]]) if m1[0] > m2[0]: return self.findMedianSortedArrays(nums1[:size1 - m2[1]],nums2[m2[1]:]) else: return m1[0]
到此，关于"Java怎么寻找两个有序数组的中位数"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！
