LeetCode Algorithm Questions by Python

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.

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

The idea is to pick up the numbers in nums2 that are smaller than a number in nums1, until we get the median.

Pay attention:
1. consider three cases: odd, even, and null;
2. max of nums1 may smaller than min of nums2;
3. use float() while doing the division.

My code in Python is as follows:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        mn = m + n
        i = 0
        acc = 0
        med2 = 0
        if m == 0 or n == 0:
            nums1.extend(nums2)
            if mn % 2 == 0:
                return float(nums1[(mn/2-1)]+nums1[mn/2])/2
            else:
                return nums1[(mn+1)/2-1]
        elif mn % 2 == 0:
            p = mn/2+1
            for n1 in nums1:
                while i < n and nums2[i] < n1:
                    med1 = med2
                    med2 = nums2[i]
                    i += 1
                    acc += 1
                    if acc == p:
                        return float(med1+med2)/2
                        break
                med1 = med2
                med2 = n1
                acc += 1
                if acc == p:
                    return float(med1+med2)/2
                    break
            if acc == p-1:
                return float(med2+nums2[acc-m])/2
            elif acc < p-1:
                return float(nums2[p-m-2]+nums2[p-m-1])/2
        else:
            p = (mn+1)/2
            for n1 in nums1:
                while i < n and nums2[i] < n1:
                    med1 = med2
                    med2 = nums2[i]
                    i += 1
                    acc += 1
                    if acc == p:
                        return med2
                        break
                med1 = med2
                med2 = n1
                acc += 1
                if acc == p:
                    return med2
                    break
            if acc < p:
                return nums2[p-m-1]