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

题目：

给定两个大小为 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

思路：

解决这道题并不难，而是满足解题要求时间复杂度为 O(log(m + n))有点困难，不过看到log字眼就想到快排，所以我们可以对两个数组进行二分处理。不过在处理是要根据两个数组的长度来区分不同的情况。

代码：

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        numstr1 = nums1
        numstr2 = nums2
        num_sum = len(numstr1) + len(numstr2)
        k = (num_sum + 1) // 2
        while k != 1:
            if k//2 > len(numstr1): #情况一   列表一的长度不足K/2
                if len(numstr1) == 0: #判断是否为空列表
                    break
                elif numstr1[len(numstr1) - 1] < numstr2[k//2 -1]:#列表一最后一个数小于列表二的第 k/2 个数 则说明第K个数不在列表一 
                    k = k - len(numstr1)
                    numstr1 = []
                else:
                    numstr2 = numstr2[k//2 ::] #缩短
                    k = k -(k // 2)
                    print(numstr2)
            elif k//2 > len(numstr2): # 情况二 列表而长度不足k/2
                if len(numstr2) == 0: #判断是否为空列表
                    break
                elif numstr2[len(numstr2) - 1] < numstr1[k//2 -1]: 
                    k = k - len(numstr2)
                    numstr2 = []
                else:
                    numstr1 = numstr1[k//2 ::]
                    k = k -(k // 2)
            else: #情况三 两个列表长度都比K/2大
                if numstr1[k//2 -1] <= numstr2[k//2 -1]:
                    numstr1 = numstr1[k//2 ::]
                    k = k -(k // 2)
                else:
                    numstr2 = numstr2[k//2 ::] #缩短
                    k = k -(k // 2)
        #判断奇偶性计算中位数
        if  num_sum & 1 == 1:
            print("is odd")
            if len(numstr1) == 0:
                avg_num = numstr2[k - 1]
            elif len(numstr2) == 0:
                avg_num = numstr1[k - 1]
            else :
                if numstr1[k - 1] < numstr2[k - 1]:
                    avg_num = numstr1[k - 1]
                else:
                    avg_num = numstr2[k - 1]
        else:
            if len(numstr1) == 0:
                avg_num = (numstr2[k - 1] + numstr2[k]) / 2.0
            elif len(numstr2) == 0:
                avg_num = (numstr1[k - 1] + numstr1[k]) / 2.0
            else:
                if numstr1[k -1] < numstr2[k-1]:
                    if len(numstr1) - 1 >= k:
                        if numstr1[k] < numstr2[k - 1]:
                            avg_num = (numstr1[k - 1] + numstr1[k]) / 2.0
                        else:
                            avg_num = (numstr1[k - 1] + numstr2[k - 1]) / 2.0
                    else:
                        avg_num = (numstr1[k - 1] + numstr2[k - 1]) / 2.0
                else:
                    if len(numstr2) - 1 >= k:
                        if numstr2[k] < numstr1[k - 1]:
                            avg_num = (numstr2[k - 1] + numstr2[k]) / 2.0
                        else :
                            avg_num = (numstr2[k - 1] + numstr1[k - 1]) / 2.0
                    else:
                        avg_num = (numstr2[k -1] + numstr1[k - 1]) / 2.0

        return avg_num