[leetcode] 4. Median of Two Sorted Arrays

[leetcode] 4. Median of Two Sorted Arrays

Description

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)).

You may assume nums1 and nums2 cannot be both empty.

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

分析一

题目的意思是：求两个有序数组的中位数。

这道题是leetcode的hard类型的题目，我当年考研的王道那本书上就有类似的题目，我之所以记得是因为那个解法我看了很久都没想明白，一直记在心上，没想到找工作刷题的时候居然碰见了类似的题目。缘分暴力解法为归并排序的变体，与归并排序不一样的是，我们只归并到mid位置，就不往下归并了，由于归并排序需要数组，因此空间复杂度为O((m+n)/2)，时间复杂度为O(m+n)

代码一

class Solution {public: double findMedianSortedArrays(vector& nums1, vector& nums2) { if(nums1.size()==0){ return medianArray(nums2); } if(nums2.size()==0){ return medianArray(nums1); } vector nums3; int m=nums1.size()+nums2.size(); int mid=m/2; int flag=!(m%2); int n1=0; int n2=0; for(int i=0;i& nums){ int n=nums.size(); if(n%2==1){ return nums[n/2]; }else{ return (nums[n/2]+nums[n/2-1])/2.0; } }};

分析二

对于一个长度为n的已排序数列a，若n为奇数，中位数为a[n / 2 + 1] , 若n为偶数，则中位数(a[n / 2] + a[n / 2 + 1]) / 2 如果我们可以在两个数列中求出第K小的元素，便可以解决该问题 不妨设数列A元素个数为n，数列B元素个数为m，各自升序排序，求第k小元素 取A[k / 2] B[k / 2] 比较， 如果 A[k / 2] > B[k / 2] 那么，所求的元素必然不在B的前k / 2个元素中(证明反证法) 反之，必然不在A的前k / 2个元素中，于是我们可以将A或B数列的前k / 2元素删去，求剩下两个数列的 k - k / 2小元素，于是得到了数据规模变小的同类问题，递归解决 如果 k / 2 大于某数列个数，所求元素必然不在另一数列的前k / 2个元素中，同上操作就好。

代码二

class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int total=m+n; if(total%2==1){ return findKth(A,m,B,n,total/2+1); }else{ return (findKth(A,m,B,n,total/2)+ findKth(A,m,B,n,total/2+1))/2; } } double findKth(int A[], int m, int B[], int n,int k){ //always assume that m is equal or smaller than n if(m>n){ return findKth(B,n,A,m,k); } if(m==0){ return B[k-1]; } if(k==1){ return min(A[0],B[0]); } //divide k into two parts int pa=min(k/2,m); int pb=k-pa; if(A[pa-1]B[pb-1]){ return findKth(A,m,B+pb,n-pb,k-pb); }else{ return A[pa-1]; } } };

代码三 (python)

有序数组可以归并遍历到（m+n）/2的位置,m为数组1的长度，n为数组2的长度，然后找出根据m+n奇偶求中位数就行了。

class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: i=0 j=0 m=len(nums1) n=len(nums2) t=(m+n+1)//2 res=0 while(t>0): if(i>=m): res=nums2[j] j+=1 elif(j>=n): res=nums1[i] i+=1 elif(nums1[i]=m): return (res+nums2[j])/2 elif(j>=n): return (res+nums1[i])/2 elif(nums1[i]

代码四 （python）

举个例子，比如 nums1 = {1, 3}，nums2 = {2, 4, 5}，K=4，要找两个数组混合中第4个数字，那么分别在 nums1 和 nums2 中找第2个数字，nums1 中的第2个数字是3，nums2 中的第2个数字是4，由于3小于4，所以混合数组中第4个数字肯定在 nums2 中，可以将 nums1 的起始位置向后移动 K/2 个。反之，淘汰 nums2 中的前 K/2 个数字，并将 nums2 的起始位置向后移动 K/2 个，并且此时的K也自减去 K/2

class Solution: def findKth(self,nums1,i,nums2,j,k): m=len(nums1) n=len(nums2) if(i>=m): return nums2[j+k-1] if(j>=n): return nums1[i+k-1] if(k==1): return min(nums1[i],nums2[j]) if(i+k//2-1 float: m=len(nums1) n=len(nums2) left=(m+n+1)//2 right=(m+n+2)//2 return (self.findKth(nums1,0,nums2,0,left)+self.findKth(nums1,0,nums2,0,right))/2

参考文献

​​[编程题]median-of-two-sorted-arrays​​​​leetcode之 median of two sorted arrays​​​​《LeetBook》leetcode题解(4): Median of Two Sorted Arrays[H]——两个有序数组中值问题​​​​LeetCode 4.寻找两个有序数组的中位数​​​​[LeetCode] 4. Median of Two Sorted Arrays 两个有序数组的中位数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。