Leetcode4-Median Of Two Sorted A

问题描述

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

算法思路

针对该问题，大致思路为先将两个列表连接，排序；然后计算新的列表元素个数；最后查找并计算中位数。有以下两种实现方式，差异在于第一种排序，会覆盖掉原来的列表；第二种排序会生成原来列表的一个副本，生成一个迭代器。总的来说，推荐第一种方法，速度更快。（136 ms < 168 ms）

代码实现

方法一：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums=nums1+nums2
        nums.sort()
        n=len(nums)
        if n%2:
            return nums[n//2]
        else:
            return (nums[n//2-1]+nums[n//2])/2

方法二：

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        c=nums1+nums2
        c=sorted(c)
        n=len(c)
        a=int((n-1)/2)
        if n%2==0:
            return (c[a]+c[a+1])/2
        else:
            return c[a]

参考资料

1. https://blog.csdn.net/data8866/article/details/62884210/ Python中的 // 与 / 的区别
2. https://stackoverflow.com/questions/22442378/what-is-the-difference-between-sortedlist-vs-list-sort
   What is the difference between sorted(list) vs list.sort()?
3. https://leetcode.com/problems/median-of-two-sorted-arrays/ median-of-two-sorted-arrays