LeetCode 4. Median of Two Sorted Arrays-蒲公英云

LeetCode 4. Median of Two Sorted Arrays

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

C/C++

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    double sum = 0.0;
    int total = nums1Size + nums2Size;
    int pos2 = total / 2;
    int pos1 = pos2 - (total%2==0);
    int i = 0,s1 = 0,s2 = 0;
    while(s1<nums1Size&&s2<nums2Size&&i<=pos2)
    {
        int tmp = nums1[s1]<nums2[s2]?nums1[s1++]:nums2[s2++];
        if(i>=pos1)sum+=tmp;
        ++i;
    }
    while(s1<nums1Size&&i<=pos2)
    {
        if(i>=pos1)sum+=nums1[s1];
        ++s1;
        ++i;
    }
    while(s2<nums2Size&&i<=pos2)
    {
        if(i>=pos1)sum+=nums2[s2];
        ++s2;
        ++i;
    }
    return pos1==pos2?sum:sum*5/10;
}

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double sum = 0.0;
    int nums1Size = nums1.length;
    int nums2Size = nums2.length;
    int total = nums1Size + nums2Size;
    int pos2 = total / 2;
    int pos1 = pos2 - (total%2==0?1:0);
    int i = 0,s1 = 0,s2 = 0;
    while(s1<nums1Size&&s2<nums2Size&&i<=pos2)
    {
        int tmp = nums1[s1]<nums2[s2]?nums1[s1++]:nums2[s2++];
        if(i>=pos1)sum+=tmp;
        ++i;
    }
    while(s1<nums1Size&&i<=pos2)
    {
        if(i>=pos1)sum+=nums1[s1];
        ++s1;
        ++i;
    }
    while(s2<nums2Size&&i<=pos2)
    {
        if(i>=pos1)sum+=nums2[s2];
        ++s2;
        ++i;
    }
    return pos1==pos2?sum:sum*5/10;
    }
}

Python

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        s = 0.0
        nums1Size = len(nums1)
        nums2Size = len(nums2)
        total = nums1Size + nums2Size
        pos2 = total // 2
        pos1 = pos2-1 if total%2==0 else pos2
        i,s1,s2 = 0,0,0
        while s1<nums1Size and s2<nums2Size and i<=pos2:
            tmp = nums1[s1]
            if nums1[s1]>nums2[s2]:
                tmp = nums2[s2]
                s2 += 1
            else: s1 += 1
            if i>=pos1:s += tmp
            i += 1
        while s1<nums1Size and i<=pos2:
            if i>=pos1:s += nums1[s1]
            s1 += 1
            i += 1
        while s2<nums2Size and i<=pos2:
            if i>=pos1:s += nums2[s2]
            s2 += 1
            i += 1
        return s if pos1==pos2 else s*5/10