LeetCode題解 - 4. Median of Two Sorted Arrays [Hard]

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

1. Code:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        i = 0
        j = 0
        total = len(nums1) + len(nums2)
        medium = total // 2
        ret_list = []
        
        while (i + j) <= medium:
            if i >= len(nums1):
                ret_list.append(nums2[j])
                j += 1
            elif j >= len(nums2):
                ret_list.append(nums1[i])
                i += 1
            elif nums1[i] < nums2[j]:
                ret_list.append(nums1[i])
                i += 1
            else:
                ret_list.append(nums2[j])
                j += 1
                
        
        if total % 2 == 0:
            return (ret_list[-1] + ret_list[-2]) / 2.0
        else:
            return ret_list[-1]

心得:
雖然題目要求要O(log(m+n))，還是先照自已的想法打一遍
可以成功送出，看來 LeetCode 只會要求正確解出問題 (很合理)
有空我再想想要怎麼用2分法

2. Code:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total = len(nums1) + len(nums2)
 
        if total % 2 == 1:
            return self.findKth(nums1, nums2, (total / 2) + 1)
        else:
            return (self.findKth(nums1, nums2, total / 2) + self.findKth(nums1, nums2, (total / 2) + 1)) / 2.0
 
    def findKth(self, list_a, list_b, k):
        """ Finding the K position of two arrays
 
        :type list_a: List[int]
        :type list_b: List[int]
        :type k: int, the K position of list_a and list_b
        """
        if len(list_a) > len(list_b):
            return self.findKth(list_b, list_a, k)
        elif len(list_a) == 0:
            return list_b[k - 1]
        elif k == 1:
            return list_a[0] if list_a[0] <= list_b[0] else list_b[0]
 
        new_pos_a = (k // 2) if (k // 2) <= len(list_a) else len(list_a)
        new_pos_b = (k // 2) if (k // 2) <= len(list_b) else len(list_b)
        if list_a[new_pos_a - 1] < list_b[new_pos_b - 1]:
            return self.findKth(list_a[new_pos_a:], list_b, k - new_pos_a)
        else:
            return self.findKth(list_a, list_b[new_pos_b:], k - new_pos_b)

心得:
花了很多時間，約於寫出來了
不過效能卻沒有很好，時間大概都花在建 List 上了吧
花了 98 ms

3. Code:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total = len(nums1) + len(nums2)
        
        if total % 2 == 1:
            return self.findKth(nums1, 0, nums2, 0, (total / 2) + 1)
        else:
            return (self.findKth(nums1, 0, nums2, 0, total / 2) + self.findKth(nums1, 0, nums2, 0, (total / 2) + 1)) / 2.0
        
    def findKth(self, list_a, pos_a, list_b, pos_b, k):
        """ Finding the K position of two arrays
        
        :type list_a: List[int]
        :type pos_a: int, the index of list_a
        :type list_b: List[int]
        :type pos_b: int, the index of list_b
        :type k: int, the K position of list_a and list_b
        """
        if (len(list_a) - pos_a) > (len(list_b) - pos_b):
            return self.findKth(list_b, pos_b, list_a, pos_a, k)
        elif len(list_a) == pos_a:
            return list_b[pos_b + k - 1]
        elif k == 1:
            return list_a[pos_a] if list_a[pos_a] <= list_b[pos_b] else list_b[pos_b]
        
        new_pos_a = (pos_a + (k // 2)) if (pos_a + (k // 2)) <= len(list_a) else len(list_a)
        new_pos_b = pos_b + k - (new_pos_a - pos_a)
        if list_a[new_pos_a - 1] < list_b[new_pos_b - 1]:
            return self.findKth(list_a, new_pos_a, list_b, pos_b, k - (new_pos_a - pos_a))
        elif list_a[new_pos_a - 1] > list_b[new_pos_b - 1]:
            return self.findKth(list_a, pos_a, list_b, new_pos_b, k - (new_pos_b - pos_b))
        else:
            return list_a[new_pos_a - 1]

心得:
如果用 index 代替，會稍微快一點點
不過差距也不大拉