周二来道算法题–leetcode-hard1
周二算法题
先看看leetcode上第一道标记为Hard的题
Median of Two Sorted Arrays
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
就是找中位数,有点像,某个班级,男生一列,女生一列,都是按照从身高生序排列,要找出全班的身高的中位数。
以下就是我写的几个方法,思路都差不多,从两个数列中取出前n个数,假设n就是连个数列长度之和的一半。废话不多说,直接上代码
#!/usr/bin/python3 class Solution: def findMedianSortedArrays(self, nums1:List[int],nums2:List[int]) ->float: nums = nums1 + nums2 nums.sort() n = len(nums) if n % 2 == 0: return (nums[n//2]+nums[n//2-1])/2 else: return nums[n//2] def findMedianSortedArraysNew(self, nums1:List[int],nums2:List[int]) ->float: n1 = len(nums1) n2 = len(nums2) n = (n1+n2)//2 i = 0 pre = 0 res = 0 while i<=n : pre = res if len(nums1) == 0: res = nums2.pop() elif len(nums2) == 0: res = nums1.pop() elif nums1[-1] >= nums2[-1]: res = nums1.pop() else: res = nums2.pop() i = i+1 if (n1+n2) % 2 == 0: return (pre+res)/2 else: return pre def findMedianSortedArraysNew2(self, nums1:List[int], nums2:List[int]) -> float: n1 = len(nums1) n2 = len(nums2) n = (n1+n2)//2 i = 0 pre = 0 res = 0 j,k = 0,0 while i<=n : pre = res if n1 == j: res = nums2[k] k = k+1 elif n2 == k: res = nums1[j] j = j +1 elif nums1[j] <= nums2[k]: res = nums1[j] j = j +1 else: res = nums2[k] k = k +1 i = i+1 if (n1+n2) % 2 == 0: return (pre+res)/2 else: return res
本以为第一个方法是偷懒的方法(用到了系统的方法sort),效果可能不好;没想到后面两个自己写的方法,还不如第一个。
方法1 88 ms 12.9 MB python3 方法2 100 ms 12.9 MB python3 方法3 96 ms 12.8 MB python3
所以,查了以下python3中sort方法的实现,发现它用到了一个名为Timsort的算法 恩,关于这个算法,打算再写几篇文章。今天算是把注册很久的账号激活了,刷刷算法题,防止脑袋生锈。
https://leetcode.com/problems/median-of-two-sorted-arrays/
Runtime: 96 ms, faster than 88.25% of Python3 online submissions for Median of Two Sorted Arrays. Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Median of Two Sorted Arrays.
欢迎大家关注我的公众号–匿名程序媛,分享挖坑、踩坑、填坑的故事。我就是一个简单的匿名程序媛
原文地址:https://segmentfault.com/a/1190000021252135
相关推荐
-
apt-get更新出现W: GPG error: http://repo.mysql.com trusty InRelease python基础
2020-6-17
-
【小工具】python 携手R 计算两组数据相关性 python基础
2019-8-27
-
Python numpy中矩阵的用法总结 python基础
2019-7-21
-
wsadmin脚本更改日志详细信息级别 python基础
2020-5-31
-
进阶篇:软件测试工程师的岗位职责 python基础
2019-10-7
-
深入细枝末节,字体反爬虫到底怎么一回事 python基础
2020-6-17
-
LeetCode 31. 下一个排列 | Python python基础
2020-6-11
-
「已结束」思否社区给粉丝送福利 精品 Python 课程快来抢 python基础
2020-6-17
-
python3读取Excel(包含合并单元格) python基础
2019-8-26
-
应用:能够快速实现的协同推荐 python基础
2019-8-29