【Python】【LeetCode】【4.寻找有序数组的中位数】

绝地灬酷狼 2022-01-31 03:11 181阅读 0赞

### 文章目录 ###

*   *   *  1.原文题目
         *  2.解题思路
         *  3.Python代码

### 1.原文题目 ###

> 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2  
> 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。  
> **哈哈！，这条件我删去了！，，，本人没弄懂时间复杂度的概念！**  
> 我看见别人的评论：难的不是这道题，难的是复杂度，如果不管复杂度，两个数组一加，一sort，分奇数偶数讨论。我就是这么简单，就用这种方法！！哈哈。

示例1

> 假设 nums1 和 nums2 不会同时为空。  
> nums1 = \[1, 3\]  
> nums2 = \[2\]  
> 则中位数是 2.0

示例1

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

### 2.解题思路 ###

*为了解决这个问题，我们需要理解 “中位数的作用是什么”。在统计中，中位数被用来：*

> 将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

### 3.Python代码 ###

# -*- coding: utf-8 -*- 
    # @Time : 2019/5/15 14:22 
    # @Author : ZXL 
    # @Site :  
    # @File : 4.寻找有序数组的中位数.py 
    # @Software: PyCharm
    
    class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            num = nums1 + nums2
            num.sort()
            n = len(num)
            if n % 2 == 0:
                i = int(n / 2 -1)
                j = i + 1
                return float(num[i] + num[j])/2
            return float(num[int((n-1)/2)])
    
    if  __name__ == "__main__":
        nums1 = [1, 2]
        nums2 = [3, -1]
        result = Solution().findMedianSortedArrays(nums1,nums2)
        print(result)