个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
26
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章Python寻找两个有序数组的中位数实例详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
python寻找两个有序数组的中位数 。
审题:
1.找出意味着这是一个查找算法题 。
2.算法复杂度log级别，就是提示你是二分查找 。
3.二分查找实现一般为递归 。
（1）递归包括递归体 （2）终止条件 。
思路:
定理:
1.有序数组中有一半的元素小于等于数组的中位数，有一半的元素大于等于中位数（如果数组中元素个数是奇数，那么这里的一半并不是严格意义的1/2） 。
2.如果我们去掉其中一个数组比中位数小的k个数，再去掉另一个数组中比中位数大的k个数，得到的合并子数组的中位数和原来的中位数相同.
eg：[1,2,3],[1,2,3] => [1,1,2,2,3,3] 。
根据定理去除元素[2,3],[1,2] => [1,2,2,3]中位数没变。我用了特殊的例子解释，你可以自行换一个试一试。如果两个的数组长度不一样的时候，不能去掉各自的一半，要去掉相同的个数，下面会细说 。
解题思路:
假设两个数组的中位数分别是a[m1],b[m2] 。
1.if a[m1] == b[m2] ，那么刚好有一半的元素小于a[m1],那么a[m1]就是要找的中位数。参考上面的列子 。
2.if a[m1] < b[m2]，根据定理1可知，这个中位数只可能出现在a[n1/2 ~ n1-1]或者b[0 ~ n2/2].也就是说合并这两个数组的中位数和原来的数组合并的数组的中位数是一样的。 根据定理2可知:
1.数组长度一样的时候，去除掉一半是合理的.
2.数组长度不一样，这么做中位数可能发生变化。解决方案就是去除掉相同个数的元素。why？假设n1 < n2, 两个数组就去掉n1/2个元素。那就不在是上面的范围（a[n1/2 ~ n1-1]或者b[0 ~ n2/2]），而是a[n1/2 ~ n1-1]或者b[0 ~ (-n1/2+n2-1)]. 。
结论就是：只能删除a的n1/2(向下取整) 。
3.if a[m1] > b[m2],和上面分析类似，中位数只能出现在a的前半段或者b的后半段。也就是说a[0 ~ n1/2]和b[n1/2 ~ n2-1]的中位数和原来的中位数相同.
参考：leetcode参考答案 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
class
solution:
def
findmediansortedarrays(
self
, nums1, nums2):
"""
:type nums1: list[int]
:type nums2: list[int]
:rtype: float
"""
m, n
=
len
(nums1),
len
(nums2)
if
m > n:
nums1, nums2, m, n
=
nums2, nums1, n, m
if
n
=
=
0
:
raise
valueerror
imin, imax, half_len
=
0
, m, (m
+
n
+
1
)
/
/
2
while
imin <
=
imax:
i
=
(imin
+
imax)
/
/
2
j
=
half_len
-
i
if
i < m
and
nums2[j
-
1
] > nums1[i]:
# i is too small, must increase it
imin
=
i
+
1
elif
i >
0
and
nums1[i
-
1
] > nums2[j]:
# i is too big, must decrease it
imax
=
i
-
1
else
:
# i is perfect
if
i
=
=
0
: max_of_left
=
nums2[j
-
1
]
elif
j
=
=
0
: max_of_left
=
nums1[i
-
1
]
else
: max_of_left
=
max
(nums1[i
-
1
], nums2[j
-
1
])
if
(m
+
n)
%
2
=
=
1
:
return
max_of_left
if
i
=
=
m: min_of_right
=
nums2[j]
elif
j
=
=
n: min_of_right
=
nums1[i]
else
: min_of_right
=
min
(nums1[i], nums2[j])
return
(max_of_left
+
min_of_right)
/
2.0
|
总结 。
以上所述是小编给大家介绍的python寻找两个有序数组的中位数，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我网站的支持！ 。
原文链接：https://www.jianshu.com/p/6eab8e87a9de 。
最后此篇关于Python寻找两个有序数组的中位数实例详解的文章就讲到这里了,如果你想了解更多关于Python寻找两个有序数组的中位数实例详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
26
4
0
全称“Java Virtual Machine statistics monitoring tool”（statistics 统计；monitoring 监控；tool 工具） 用于监控虚拟机的各种运
主要是讲下Mongodb的索引的查看、创建、删除、类型说明，还有就是Explain执行计划的解释说明。 可以转载，但请注明出处。
1>单线程或者单进程 相当于短链接，当accept之后，就开始数据的接收和数据的发送，不接受新的连接，即一个server，一个client 不存在并发。 2>循环服务器和并发服务器
详解 linux中的关机和重启命令 一 shutdown命令 shutdown [选项] 时间 选项： ?
首先，将json串转为一个JObject对象： ? 1
matplotlib官网 matplotlib库默认英文字体 添加黑体（‘SimHei'）为绘图字体 代码： plt.rcParams['font.sans-serif']=['SimHei'
在并发编程中，synchronized关键字是常出现的角色。之前我们都称呼synchronized关键字为重量锁，但是在jdk1.6中对synchronized进行了优化，引入了偏向锁、轻量锁。本篇
一般我们的项目中会使用1到2个数据库连接配置，同程艺龙的数据库连接配置被收拢到统一的配置中心，由DBA统一配置和维护，业务方通过某个字符串配置拿到的是Connection对象。
实例如下： ? 1
1. MemoryCahe NetCore中的缓存和System.Runtime.Caching很相似，但是在功能上做了增强，缓存的key支持object类型；提供了泛型支持；可以读缓存和单个缓存
argument是javascript中函数的一个特殊参数，例如下文，利用argument访问函数参数，判断函数是否执行 复制代码 代码如下: <script
一不小心装了一个Redis服务，开了一个全网的默认端口，一开始以为这台服务器没有公网ip，结果发现之后悔之莫及啊 某天发现cpu load高的出奇，发现一个minerd进程 占了大量cpu，googl
今天写这个是为了 提醒自己 编程过程 不仅要有逻辑 思想 还有要规范 代码 这样可读性 1、PHP 编程规范与编码习惯最主要的有以下几点： 1 文件说明 2 funct
摘要：虚拟机安装时一般都采用最小化安装，默认没有lspci工具。一台测试虚拟网卡性能的虚拟机，需要lspci工具来查看网卡的类型。本文描述了在一个虚拟机中安装lspci工具的具体步骤。 由于要测试
1、修改用户进程可打开文件数限制 在Linux平台上，无论编写客户端程序还是服务端程序，在进行高并发TCP连接处理时，最高的并发数量都要受到系统对用户单一进程同时可打开文件数量的限制(这是因为系统
目录 算术运算符 基本四则运算符 增量赋值运算符 自增/自减运算符 关系运算符 逻
如下所示： ? 1
MapperScannerConfigurer之sqlSessionFactory注入方式讲解 首先，Mybatis中的有一段配置非常方便，省去我们去写DaoImpl（Dao层实现类）的时间，这个
Linux的网络虚拟化是LXC项目中的一个子项目，LXC包括文件系统虚拟化，进程空间虚拟化，用户虚拟化，网络虚拟化，等等，这里使用LXC的网络虚拟化来模拟多个网络环境。 本文从基本的网络设备讲
? 1
我是一名优秀的程序员,十分优秀！