LeetCode:寻找两个正序数组的中位数----多种解题方式

文章目录

• • 题目
  • 举例
  • 思路一 运用归并排序的思想，双指针
  • 思路二 运用归并排序的思想，双指针
  • 思路三 使用二分查找法

    写在前面：在学习算法中我们会学到很多经典的算法，双指针，二分查找等等，但是这只是一种思想，解题时我们可以灵活的运用，也不必局限一种形式，要将学到的东西，转换成自己的东西。

    题目

    给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

    算法的时间复杂度应该为 O(log (m+n))

    举例

    实例1：

    输入：nums1 = [1,3], nums2 = [2]
    输出：2.00000
    解释：合并数组 = [1,2,3] ，中位数 2
    

    实例2：

    输入：nums1 = [1,2], nums2 = [3,4]
    输出：2.50000
    解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
    

    注意本题在力扣中不用返回的数据不用考虑小数位数，系统会自动保留对应的位数

    思路一 运用归并排序的思想，双指针

    因为这是两个有序数组，在两个有序数组中寻找中位数，可以先考虑将两个数组合并起来，然后找中位数

    有序数组的合并比较简单，就是用两个指针分别指向两个数组的开头，依次比较指针指向的数字，较少的数字添加到新数组，指针加1，然后再重复以上的循环，直至其中一个指针越界。最后将未添加完的数字合并到新数组中

    详细的流程看代码

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l1 = 0
        l2 = 0
        r1 = len(nums1)
        r2 = len(nums2)
        arr = []
        while True:  # 循环添加
            if l1>r1-1 or l2>r2-1:  # 当有一个数组的数据被添加完成，就跳出循环
                break
            if nums1[l1] > nums2[l2]:
                arr.append(nums2[l2])
                l2+=1
            else:
                arr.append(nums1[l1])
                l1+=1
    	# 添加未合并完成的数组
        if l1!=r1:
            arr.extend(nums1[l1:])
        elif l2!=r2:
            arr.extend(nums2[l2:])
        # 根据数组长度的奇偶返回不同的值
        if (r1+r2)%2==0:
            return (arr[((r1+r2)//2)-1]+arr[(r1+r2)//2])/2
        else:
            return arr[(r1+r2)//2]
    

    我们能发现上面这个解题方式中，我们使用了额外的一个数组，浪费了内存空间，因为是两个有序数组，目的又是找出中位数，所以我们可以直接找出中位数，而不用进行合并

    思路二 运用归并排序的思想，双指针

    这个算法也是用了两个指针，使用情况同第一个类似，只不过我们比较大小后不进行合并，就是用应给变量记录比较的次数，直至比较的次数==中位数的位置，此时我们再根据具体的情况返回具体的值

    具体的思路请看代码

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        l1 = 0 
        l2 = 0
        r1 = len(nums1)
        r2 = len(nums2)
        number = 0   # 记录次数
        f = 0 # 标志数组是奇数还是偶数
        
        # 根据奇偶设置中间的元素位置
        if (r1+r2)%2==0: 
            f = 2
            mid = (r1+r2)//2   
        else:
            f = 1
            mid = (r1+r2)//2+1
            
        while True:
            if l1>r1-1 or l2>r2-1:
                break
            if nums1[l1] > nums2[l2]: 
                number+=1
                if number == mid: # 当number等于mid的时候就代表此时已经到了中位数的位置
                    if f==1:   # 奇数情况
                        return nums2[l2]  
                    else:      # 偶数情况
                        if l2==r2-1:  # 此时l2指向其中nums2的最后一个元素
                            return (nums2[l2]+nums1[l1])/2
                        else:
                        	# 返回两种情况中最小的
                            return min(nums2[l2]+nums2[l2+1],nums2[l2]+nums1[l1])/2
                l2+=1 
            else:   # 同上思想一样，对象更换了一下
                number+=1
                if number == mid:
                    if f==1:
                        return nums1[l1]
                    else:
                        if l1==r1-1:
                            return (nums2[l2]+nums1[l1])/2
                        else:       
                            return min(nums1[l1]+nums1[l1+1],nums2[l2]+nums1[l1])/2
                l1+=1
            
        # 这种是当一个数组特别长，中位数在其中一个数组中的情况
        if l1!=r1:
            if f==1:
                return nums1[mid-l2-1]
            else:
                return (nums1[mid-l2-1]+nums1[mid-l2])/2
        elif l2!=r2:
            if f==1:
                return nums2[mid-l1-1]
            else:
                return (nums2[mid-l1-1]+nums2[mid-l1])/2
    

    此时我们能够发现上面的两种解法的时间复杂度不是 O(log (m+n))，原因就是我们合并和排除数字都是一个一个的进行的 时间复杂度为 O(m+n)

    想要实现O(log (m+n))的时间复杂度，我们可以回想一下什么情况出现log，二分法，此时我们的思路就明朗了，解题需要使用二分的思想，每次排除的数字，都应该是原数据的二分之一

    思路三 使用二分查找法

    

    

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
        	# 保证数组nums1是较短的哪一个
            return self.findMedianSortedArrays(nums2, nums1)
        infinty = 10*6+1  # 
        m, n = len(nums1), len(nums2)
        left, right = 0, m  # 只需要记录记录第一个数组的指针，第二个数组可以计算出来
        # median1：前一部分的最大值
        # median2：后一部分的最小值
        median1, median2 = 0, 0
        while left