About

挑战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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

解题思路

采用了双指针法，分别指向两个数组的头部，然后通过条件判断来断定指针是否后移，后移的同时将元素insert或者append进入新的列表，最后求列表的中位数。

1. 先判断传入的列表是否为空（题目说假设两个列表不同时为空，所以这里只判断一个列表），如果列表为空，则返回另一列表的中位数
2. 因为后面的循环逻辑涉及到判断指针指向的列表元素的值和新列表的最后一个元素的比较，所以在这里先判断传入的两个列表的第一个元素的大小，谁小就把谁的第一个元素append进新列表，并且指针+1
3. 进入while循环，循环的跳出条件为某一列表遍历完毕
4. 在循环中先判断nums1[p]与新列表的最后一个元素的大小，如果nums1[p] < result[-1]，那么nums2[q] 必然大于result[-1]，所以此时只需要将nums1[p]插入到新列表的倒数第二个位置，p自增1
5. 否则如果nums2[q] < result[-1]，此时只需要将nums1[p]插入到新列表的倒数第二个位置，q自增1
6. 如果nums1[p]、nums2[q]都大于新列表的最后一个元素，则判断他俩谁小就把谁追加到新列表的尾部。
7. 循环结束后需要判断是哪一个列表遍历完毕，把未遍历完毕的列表拼接到新列表中
8. 对新列表求中位数。

我可能叙述的不是很清楚，但是代码易懂哦~~~

代码如下（python3）

#-*- coding:utf-8 -*-
#Author: Bing Xu

class Solution(object):
    def findMid(self, s):
        mid = ''
        length = len(s)
        if length % 2:
            mid = s[length // 2]
        else:
            mid = (s[length // 2] + s[length // 2 - 1]) / 2
        return mid

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        result = []
        p = q = 0
        len1 = len(nums1)
        len2 = len(nums2)
        if len1 == 0:
            return self.findMid(nums2)
        if len2 == 0:
            return self.findMid(nums1)
        if nums1[0] >= nums2[0]:
            result.append(nums2[0])
            q += 1
        else:
            result.append(nums1[0])
            p += 1
        while p < len1 and q < len2:
            if nums1[p] < result[-1]:
                result.insert(-1, nums1[p])
                p += 1
            elif nums2[q] < result[-1]:
                result.insert(-1, nums2[q])
                q += 1
            elif nums1[p] >= nums2[q]:
                result.append(nums2[q])
                q += 1
            else:
                result.append(nums1[p])
                p += 1
        if p == len1:
            result.extend(nums2[q:])
        else:
            result.extend(nums1[p:])
        return self.findMid(result)

运行结果

Runtime: 60 ms, faster than 62.01% of Python3 online submissions for Median of Two Sorted Arrays.
Memory Usage: 13.4 MB, less than 42.43% of Python3 online submissions for Median of Two Sorted Arrays.

优秀题解

不写了！我最优秀，哼😒