美文网首页
4.寻找两个有序数组的中位数-findMedianSortedA

4.寻找两个有序数组的中位数-findMedianSortedA

作者: 赵苏苏_5d86 | 来源:发表于2019-08-19 11:00 被阅读0次

    链接

    LeeCode-4-寻找两个有序数组的中位数

    参考

    Git

    题目描述

    给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
    你可以假设 nums1 和 nums2 不会同时为空。

    示例:

    示例 1:
    nums1 = [1, 3]
    nums2 = [2]
    则中位数是 2.0

    示例 2:
    nums1 = [1, 2]
    nums2 = [3, 4]
    则中位数是 (2 + 3)/2 = 2.5

    实现(python3)

    总长度奇偶分别处理

    class Solution():
        def findMedianSortedArrays(self, a, b):
            n = len(a) + len(b)
            if n&1:
                return self.kthSmallest(a,b,n//2+1)
            else:
                return (self.kthSmallest(a,b,n//2+1) + self.kthSmallest(a,b,n//2))/2.0
    
        def kthSmallest(self, a, b, k):
            if len(a) + len(b) < k:
                return None
            i = 0
            j = 0
            flag = True
            while k > 0:
                if i >= len(a):
                    j += 1
                    flag = False
                elif j >= len(b):
                    i += 1
                    flag = True
                elif a[i] <= b[j]:
                    i += 1
                    flag = True
                elif a[i] > b[j]:
                    j += 1
                    flag = False
    
                k -= 1
            if flag:
                return a[i-1]
            else:
                return b[j-1]
    

    相关文章

      网友评论

          本文标题:4.寻找两个有序数组的中位数-findMedianSortedA

          本文链接:https://www.haomeiwen.com/subject/muzadctx.html