two sort array O(log(m+n)) 时间内 求中间值

前端之家收集整理的这篇文章主要介绍了two sort array O(log(m+n)) 时间内 求中间值前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

<table class="ruby"><tr class="li1">
<td class="ln"><pre class="de1">1
2
3
4
5
6
7
8
@H_301_1@</td>
<td class="de1"><pre class="de1"><span class="kw1">def find_median_sorted_arrays<span class="br0">(nums1,nums2<span class="br0">)
  a,b = <span class="br0">[nums1,nums2<span class="br0">].<span class="me1">sortby<span class="br0">(<span class="sy0">&:size<span class="br0">)
  m,n = a.<span class="me1">size,b.<span class="me1">size
  after = <span class="br0">(m <span class="sy0">+ n <span class="sy0">- <span class="nu0">1<span class="br0">) <span class="sy0">/ <span class="nu0">2
  i = <span class="br0">(<span class="nu0">0...<span class="me1">m<span class="br0">).<span class="me1">bsearch <span class="br0">{ <span class="sy0">|i<span class="sy0">| after<span class="sy0">-i<span class="sy0">-<span class="nu0">1 <span class="sy0">< <span class="nu0">0 <span class="sy0">|| a<span class="br0">[i<span class="br0">] <span class="sy0">>= b<span class="br0">[after<span class="sy0">-i<span class="sy0">-<span class="nu0">1<span class="br0">] <span class="br0">} <span class="sy0">|| m
  nextfew = <span class="br0">(a<span class="br0">[i,<span class="nu0">2<span class="br0">] <span class="sy0">+ b<span class="br0">[after<span class="sy0">-i,<span class="nu0">2<span class="br0">]<span class="br0">).<span class="me1">sort
  <span class="br0">(nextfew<span class="br0">[<span class="nu0">0<span class="br0">] <span class="sy0">+ nextfew<span class="br0">[<span class="nu0">1 <span class="sy0">- <span class="br0">(m<span class="sy0">+n<span class="br0">)<span class="sy0">%2<span class="br0">]<span class="br0">) <span class="sy0">/ <span class="nu0">2.0
<span class="kw1">end@H
301_1@</td>
</tr></table>

猜你在找的程序笔记相关文章