Leetcode 4. Median of Two Sorted Arrays-白红宇

Leetcode 4. Median of Two Sorted Arrays

阅读量：5769 次

发布时间：2019-06-18

本文共 1453 字，大约阅读时间需要 4 分钟。

https://leetcode.com/problems/median-of-two-sorted-arrays/

Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]nums2 = [2]The median is 2.0

Example 2:

nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5

题目要求O( log(m+n) )，先写了个O( (m+n)log(m+n) )凑数。

Built-in Functions — Python 3.7.2 documentation
- https://docs.python.org/3/library/functions.html#sorted
- sorted(iterable, *, key=None, reverse=False)

Sorting HOW TO — Python 3.7.2 documentation
- https://docs.python.org/3/howto/sorting.html#sortinghowto
- Python lists have a built-in method that modifies the list in-place. There is also a built-in function that builds a new sorted list from an iterable.
- In this document, we explore the various techniques for sorting data using Python.

1 class Solution: 2     def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: 3         merge_nums = sorted( nums1 + nums2 ) # pay attention to the parameter 4          5         n_nums = len( merge_nums ) 6         index = int( n_nums / 2 ) 7          8         if n_nums % 2 == 0:     9             return ( merge_nums[ index ] + merge_nums[ index - 1 ] ) / 210         else:11             return ( merge_nums[ index ] )

View Code