[LeetCode] 4. Median of Two Sorted Arrays(Python)
2021/12/6 22:17:07
本文主要是介绍[LeetCode] 4. Median of Two Sorted Arrays(Python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
[LeetCode] 4. Median of Two Sorted Arrays(Python)
- 1. 题目
- 2. 题目理解
- 3. 代码实现
1. 题目
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
Example 3:
Input: nums1 = [0,0], nums2 = [0,0] Output: 0.00000
Example 4:
Input: nums1 = [], nums2 = [1] Output: 1.00000
Example 5:
Input: nums1 = [2], nums2 = [] Output: 2.00000
Constraints:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
2. 题目理解
输入两个排好序的数组,返回两个数组的中位数,时间复杂度为O(log (m+n))。
3. 代码实现
1)思路一
将两个数组混为一个数组并排序,若共有偶数位,则取两个中间值的均值,否则输出中值。
class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ m,n = len(nums1), len(nums2) nums = sorted(nums1 + nums2) med = int((m+n)/2) if (m+n)%2 == 0: return float(nums[med-1] + nums[med]) / 2 else: return float(nums[med])
分析:使用了库函数sorted(),因此时间复杂度与此库函数有关。
2)思路二
引入寻找第k小的数的函数来避免一些冗余。在getKth()函数中,所有操作在第一个数组长度小于等于第二个的逻辑上产生。若第一个数组为空,则直接输出第二个数组的第k位。若k为1,则输出两个数组第一位中较小的数。k大于1时,对两个数组的k/2位开始比较,若A[k/2]较小,则比A[k/2]小的数最多有k-2个,所以A[k/2]前的数可以被放弃,操作的数组变为(A[k/2:], B, pb),A[k/2]较大时想法类似,抛弃B数组后半部份的数。
class Solution(object): def getKth(self, A, B, k): lenA, lenB = len(A), len(B) if lenA > lenB: return self.getKth(B, A, k) if lenA == 0: return B[k - 1] if k == 1: return min(A[0], B[0]) posi_a = min(k/2, lenA) posi_b = k - posi_a if A[posi_a - 1] <= B[posi_b - 1]: return self.getKth(A[posi_a:], B, posi_b) else: return self.getKth(A, B[posi_b:], posi_a) def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ len1, len2 = len(nums1), len(nums2) if (len1 + len2) % 2 == 1: return self.getKth(nums1, nums2, (len1+len2)/2 + 1) else: return (self.getKth(nums1, nums2, (len1+len2)/2) + self.getKth(nums1, nums2, (len1+len2)/2 + 1)) * 0.5
这篇关于[LeetCode] 4. Median of Two Sorted Arrays(Python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python