Leetcode 4. Median of Two Sorted Arrays (python+cpp)

题目

解法1：双指针

版本一：time complexity O(m+n)，space complexity O(m+n)

class Solution {
    
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();int p1 = 0, p2 = 0;vector<int> res;while(p1<m && p2<n){
    if(nums1[p1]<nums2[p2]){
    res.push_back(nums1[p1]);p1++;}else{
    res.push_back(nums2[p2]);p2++;}}while(p1<m){
    res.push_back(nums1[p1]);p1++;}while(p2<n){
    res.push_back(nums2[p2]);p2++;}if((m+n)%2 == 0){
    return (double)(res[(m+n)/2]+res[(m+n)/2-1])/2;}else{
    return res[(m+n)/2];}}
};

版本二：time complexity O(m+n)，space complexity O(1)

class Solution {
    
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();int n = nums2.size();int p1 = 0,p2 = 0,count = 0;int tmp1 = 0, tmp2 = 0;while (p1<m && p2<n){
    count += 1;if (nums1[p1]<nums2[p2]){
    if (count == (m+n)/2){
    tmp1 = nums1[p1];}if (count == (m+n)/2 + 1){
    tmp2 = nums1[p1];}p1++;}else{
    if (count == (m+n)/2){
    tmp1 = nums2[p2];}if (count == (m+n)/2 + 1){
    tmp2 = nums2[p2];}p2++;}}while(p1<m){
    count++;if (count == (m+n)/2){
    tmp1 = nums1[p1];}if (count == (m+n)/2 + 1){
    tmp2 = nums1[p1];}p1++;}while(p2<n){
    count++;if (count == (m+n)/2){
    tmp1 = nums2[p2];}if (count == (m+n)/2 + 1){
    tmp2 = nums2[p2];}p2++;}if ((m+n)%2 != 0) return tmp2;// cout << tmp1 << tmp2 << endl;return (double)(tmp1+tmp2)/2;}
};

解法2：binary search

参考：https://medium.com/@hazemu/finding-the-median-of-2-sorted-arrays-in-logarithmic-time-1d3f2ecbeb46
二分搜索的值为两个数组向merge后的数组的前一半贡献多少个值

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:A,B = nums1,nums2m,n = len(A),len(B)#将搜索范围定为长度小的那个数组if m>n:A,B,m,n = B,A,n,m#half_len代表中位数所在merge后数组中的index，必须是(m+n+1)/2，而不是(m+n)/2#举几个例子就可以明白了imin,imax,half_len = 0,m,(m+n+1)//2#对长度小的数组进行二分搜索，找出这个数组向merge后的数组贡献了多少个元素while imin<=imax:#假设i为短数组贡献的元素个数，j为另一个数组贡献的个数i = (imin+imax)//2j = half_len-i#所以现在假设的是A贡献的最后一个元素是A[i-1],但是如果A贡献的最后一个元素的下一个元素#比B[j-i]也就是比B贡献的最后一个元素还小，说明A需要贡献更多的元素if i<m and B[j-1]>A[i]:imin = i+1#同理，如果B贡献的最后一个元素B[j-i]的下一个元素B[j]比A贡献的最后一个元素A[i-1]还小，#那么说明A贡献的元素太多了elif i>0 and A[i-1] > B[j]:imax = i-1#此外的情况，说明我们已经正确的找到了A贡献的元素个数i，和B贡献的元素个数j，也就是#half_len-i个else:#接下来分两种情况，两个数组加起来个数是奇数，只需要找出A和B贡献的最后两个元素中最大#值，也就是min(A[i-1],B[j-1]).但是这里A贡献0个元素和B贡献0个元素的情况需要分开考虑if i==0: max_of_left = B[j-1]elif j==0: max_of_left = A[i-1]else: max_of_left = max(A[i-1],B[j-1])#两个数组加起来元素个数是奇数的时候，直接返回max_len_leftif (m+n)%2 == 1:return max_of_left#如果是偶数，则说明我们现在贡献的所有元素刚好是总的元素个数的一半，那么中位数就是#已经贡献的所有元素中的最大值，也就是前面求出的max_len_left，和下一个会被贡献的元素#的均值if i==m: min_of_right = B[j]elif j==n: min_of_right = A[i]else: min_of_right = min(A[i],B[j])return (max_of_left+min_of_right)/2.0