LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数 by hughie8

View this thread on steempeak.com
esteem · @hughie8 ·
$0.46
LeetCode 4 | 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

## 分析

算中位数，在我们平时的思路上， 就是把一组无序的数， 排序， 取位置在最中间的数，如果数组有偶数个数， 就取中间两个数的平均数

因此最容易想到的方法是， 把数组 nums1 和数组 nums2 合并起来， 然后使用sort()方法排序， 取中间数即可。

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // 合并
    let nums = nums1.concat(nums2)
    // 排序
    nums.sort(function(a, b) { return a-b })
    let l = nums.length
    // 偶数个 返回中间两数平均值
    if (l % 2 === 0) {
        return (nums[l / 2 - 1] + nums[l / 2]) / 2
    } else {
    // 奇数个 返回中间的数
        return nums[parseInt(l / 2)]
    }
};
```

但这样解其实是不符合题意的， 因为题目限定了时间复杂度为O(log(m + n))， 这是一个log级别的复杂度， 显然是不能使用任何排序算法的，这也是这个题目难度是困难的原因

这道题我是不会的， 因为我没有想到中位数另外一个定义：
将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

也就是说， 这是一种分而治之的思想， 如果num1长度为3， nums2长度为4， 我们可以从中间对nums1数组切一刀， 假设切一刀后, nums1左侧的元素个数为 1 个, 那么根据中位数定义中“将一个集合划分为两个长度相等的子集”，可以知道 ，此时num2左侧的元素个数一定要为 6， 因为只有这样切，才可以保证两边元素个数相等。

    left      |        right
    nums1[0], nums1[1], ..., nums1[i-1]  |  nums1[i], nums1[i+1], ..., nums1[m-1]
    nums2[0], nums2[1], ..., nums2[j-1]  |  nums2[j], nums2[j+1], ..., nums2[n-1]

假设 L1 为 nums1 切面左侧的最后一个元素 num1[i - 1]， R2为 nums2切面右侧第一个元素nums[j]， 那么根据定义“其中一个子集中的元素总是大于另一个子集中的元素”可知 L1 一定要 小于 R2， 同理 L2一定要小于 R1， 如果不满足， 就要用到二分查找， 更新切面的位置，直到满足这两个定义：
- 两个长度相等的子集 即 分别切开后， nums1和nums2左侧元素个数和右侧元素个数要相等
- 其中一个子集中的元素总是大于另一个子集中的元素。即 L1 < R2, L2 < R1

寻找到满足条件的切点后， 计算中位数，如果是奇数个， 取nums1, nums2左侧较大的数， 右侧较小的数，取平均值 如果是偶数个， 取右侧较小值即为所求


## Javascript解法

```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
   var findMedianSortedArrays = function(nums1, nums2) {
   
    // 过滤边界情况
    let l1 = nums1.length, l2 = nums2.length
    if(l1 === 0 && l2 === 1) { return nums2[0] }
    if (l2 === 0 && l1 === 1) { return nums1[0] }
    if (l1 === 1 && l2 === 1) { return (nums1[0] + nums2[0]) / 2 }

     // 如果第一个数组长度大于第二个， 则把他们顺序颠倒 运行函数
     // 因为知道了nums1在哪儿切， 就知道了nums2在哪儿切， 因此选数组长度小的切节省时间
    if(nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1)
    }
    
   
    // 二分查找切点位置的左右边界
    let cutL = 0
    let cutR = nums1.length
    
    let cut1 = 0, cut2 = 0
    // 二分查找
    while(cutL <= cutR) {
    // 根据中位数的特征 两个数组合起来的中位数， 在数组的中间位置切开
   // 如果nums1 + nums2的总长度是5， 假设从nums1第二个位置切开，
   // nums1被切开的左侧有两个元素， 那么直接就可知道, 此时nums2在第三
   // 个位置被切开
        cut1 = parseInt((cutR - cutL) / 2) + cutL
        cut2 = parseInt((l1 + l2) / 2) - cut1
        // 分别计算切面两侧的元素L1, L2, R1, R2
        let L1 = (cut1 === 0) ? -Infinity : nums1[cut1 - 1]
        let L2 = (cut2 === 0) ? -Infinity : nums2[cut2 - 1]
        let R1 = (cut1 === l1) ? Infinity : nums1[cut1]
        let R2 = (cut2 === l2) ? Infinity : nums2[cut2]
        // 如果左侧大于了右侧， 说明该切点切得太靠后， 减少右边界
        if (L1 > R2) {
            cutR = cut1 - 1
        } else if (L2 > R1) {
            // 如果右侧大于左侧， 说明切点太靠前， 增加左边界
            cutL = cut1 + 1
        } else {
            // 当满足情况时， 取L1 L2中的最大的， R1,R2中最小的，即为合成后的数组的中间两数 如果数量为偶数个 返回均值
            if ((l1 + l2) % 2 === 0) {
                L1 = L1 > L2 ? L1 : L2
                R1 = R1 < R2 ? R1 : R2
                return (L1 + R1) / 2
            } else {
                // 如果是奇数个， 按照规律 直接返回R1 R2中的较大者即为所求
                R1 = R1 < R2 ? R1 : R2
                return R1
            }
        }
    }
    return -1
};
```

## 运行结果
![x1dpf7iozr.png](https://img.esteem.ws/x1dpf7iozr.png)
👍  , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , and 20 others
properties (23)
post_id76,306,923
authorhughie8
permlinkleetcode-4-or-median-of-two-sorted-arrays
categoryesteem
json_metadata{"image":["https:\/\/img.esteem.ws\/x1dpf7iozr.png"],"users":["param","param","return","param","param","return"],"tags":["esteem","cn","programming","cnstm","partiko"],"app":"esteem\/2.1.0-surfer","format":"markdown+html","community":"esteem.app"}
created2019-06-13 03:55:00
last_update2019-06-13 03:55:00
depth0
children13
net_rshares850,988,566,878
last_payout2019-06-20 03:55:00
cashout_time1969-12-31 23:59:59
total_payout_value0.344 SBD
curator_payout_value0.114 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length3,753
author_reputation107,977,516,232
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries
0.
accountesteemapp
weight1,000
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
author_curate_reward""
vote details (84)
@drotto · 
<p>This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.</p>
properties (22)
post_id76,307,572
authordrotto
permlinkre-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t041342961z
categoryesteem
json_metadata{"tags":["esteem"],"app":"drotto\/0.0.5pre2"}
created2019-06-13 04:13:42
last_update2019-06-13 04:13:42
depth1
children0
net_rshares0
last_payout2019-06-20 04:13:42
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length80
author_reputation424,402,347,817
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@lovejuice ·
re-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t043205757z
This post has received a 27.25% upvote from @lovejuice thanks to @hughie8. They love you, so does Aggroed. Please be sure to vote for Witnesses at https://steemit.com/~witnesses.
properties (22)
post_id76,308,161
authorlovejuice
permlinkre-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t043205757z
categoryesteem
json_metadata{"app":"postpromoter\/1.7.4"}
created2019-06-13 04:32:06
last_update2019-06-13 04:32:06
depth1
children0
net_rshares0
last_payout2019-06-20 04:32:06
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length178
author_reputation10,525,002,852,777
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@honestbot ·
re-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t043949600z
You just received a 14.39% upvote from @honestbot, courtesy of @hughie8!
![WaveSmall.gif](https://steemitimages.com/DQmaHNChXJe14nWPwWdsrXEG2M3jSBRpDpF4cwq1ERhS3d4/WaveSmall.gif)
properties (22)
post_id76,308,474
authorhonestbot
permlinkre-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t043949600z
categoryesteem
json_metadata{"app":"postpromoter\/1.8.6"}
created2019-06-13 04:39:48
last_update2019-06-13 04:39:48
depth1
children0
net_rshares0
last_payout2019-06-20 04:39:48
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length179
author_reputation-221,026,549,797
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@davidke20 · 
赞如果是买的就不好了。#esteem 有抽成10%

Posted using [Partiko Android](https://partiko.app/referral/davidke20)
properties (22)
post_id76,309,865
authordavidke20
permlinkdavidke20-re-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t052653866z
categoryesteem
json_metadata{"app":"partiko","client":"android"}
created2019-06-13 05:26:54
last_update2019-06-13 05:26:54
depth1
children1
net_rshares0
last_payout2019-06-20 05:26:54
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length97
author_reputation317,850,004,724,810
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@hughie8 · 
(⊙o⊙)哦 我不知道哦，， 多谢告知、
我也是刚装了eSteem试试， 感觉界面好看
小买 都是minimum payment, 花的少， 主要为了reputation提的快
properties (22)
post_id76,310,205
authorhughie8
permlinkre-davidke20-2019613t133719660z
categoryesteem
json_metadata{"tags":["esteem"],"app":"esteem\/2.1.0-surfer","format":"markdown+html","community":"esteem.app"}
created2019-06-13 05:37:42
last_update2019-06-13 05:37:42
depth2
children0
net_rshares0
last_payout2019-06-20 05:37:42
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length88
author_reputation107,977,516,232
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries
0.
accountesteemapp
weight1,000
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@esteemapp · 
Thanks for using **eSteem**! <br>Your post has been voted as a part of [eSteem encouragement program](https://steemit.com/esteem/@good-karma/encouragement-program-continues-82eafcd10a299). Keep up the good work! Install [Android](https://play.google.com/store/apps/details?id=app.esteem.mobile), [iOS](https://itunes.apple.com/WebObjects/MZStore.woa/wa/viewSoftware?id=1451896376&mt=8) Mobile app or [Windows, Mac, Linux](https://github.com/esteemapp/esteem-surfer/releases) Surfer app, if you haven't already!<br>Learn more: https://esteem.app <br>Join our discord: https://discord.gg/8eHupPq
properties (22)
post_id76,309,928
authoresteemapp
permlinkre-2019613t72850990z
categoryesteem
json_metadata{"tags":["esteem"],"app":"esteem\/2.0-welcome","format":"markdown+html","community":"esteem.app"}
created2019-06-13 05:28:51
last_update2019-06-13 05:28:51
depth1
children0
net_rshares0
last_payout2019-06-20 05:28:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length593
author_reputation396,075,316,369,469
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@cnbuddy · 
你那里天气如何？来一份新手村小卖部的美食吧！@teamcn-shop倘若你想让我隐形，请回复“取消”。
properties (22)
post_id76,312,832
authorcnbuddy
permlinkre-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t065610036z
categoryesteem
json_metadata{}
created2019-06-13 06:56:09
last_update2019-06-13 06:56:09
depth1
children0
net_rshares0
last_payout2019-06-20 06:56:09
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length51
author_reputation-1,405,328,253,928
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@teamcn-shop · 
你好鸭，hughie8!

@cnbuddy给您叫了一份外卖！

由 @sasaadrian 一灯大师 迎着沙尘暴 跑着步 念着软哥金句:"别以为你长的稀有样我们就应该物以稀为贵。" 给您送来
**大闸蟹** <br> ![](https://ipfs.busy.org/ipfs/QmZj19fJn4VEhW8B8tsuTC5Vu5prfUj3CnwPYDhmFDNVPD)
吃饱了吗？跟我猜拳吧！ **石头，剪刀，布～**

如果您对我的服务满意，请不要吝啬您的点赞～
@onepagex
properties (22)
post_id76,312,836
authorteamcn-shop
permlinkre-hughie8-leetcode-4-or-median-of-two-sorted-arrays-20190613t065610036z
categoryesteem
json_metadata"{"app":"teamcn-shop bot\/1.0"}"
created2019-06-13 06:56:15
last_update2019-06-13 06:56:15
depth1
children2
net_rshares0
last_payout2019-06-20 06:56:15
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length247
author_reputation66,748,950,931,416
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@hughie8 · 
石头
properties (22)
post_id76,419,686
authorhughie8
permlinkpt4gue
categoryesteem
json_metadata{"tags":["esteem"],"app":"steemit\/0.1"}
created2019-06-15 04:08:42
last_update2019-06-15 04:08:42
depth2
children1
net_rshares0
last_payout2019-06-22 04:08:42
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length2
author_reputation107,977,516,232
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@teamcn-shop · 
https://4.bp.blogspot.com/-mmW-s8jFGGo/WoGwFCWm5jI/AAAAAAATXI4/T9UiUyrg7acAFnpPigWlgbdyo-Cb4M8AgCLcBGAs/s1600/AW785125_15.gif 
 You win!!!! 你赢了！ 给你1枚SHOP币！
properties (22)
post_id76,419,687
authorteamcn-shop
permlinkpt4gue
categoryesteem
json_metadata"{"app":"teamcn-shop bot\/1.0"}"
created2019-06-15 04:08:48
last_update2019-06-15 04:08:48
depth3
children0
net_rshares0
last_payout2019-06-22 04:08:48
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length155
author_reputation66,748,950,931,416
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@steemitboard · 
Congratulations @hughie8! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :

<table><tr><td><img src="https://steemitimages.com/60x70/http://steemitboard.com/@hughie8/voted.png?201906130534"></td><td>You received more than 500 upvotes. Your next target is to reach 1000 upvotes.</td></tr>
</table>

<sub>_You can view [your badges on your Steem Board](https://steemitboard.com/@hughie8) and compare to others on the [Steem Ranking](https://steemitboard.com/ranking/index.php?name=hughie8)_</sub>
<sub>_If you no longer want to receive notifications, reply to this comment with the word_ `STOP`</sub>



###### [Vote for @Steemitboard as a witness](https://v2.steemconnect.com/sign/account-witness-vote?witness=steemitboard&approve=1) to get one more award and increased upvotes!
properties (22)
post_id76,319,542
authorsteemitboard
permlinksteemitboard-notify-hughie8-20190613t095553000z
categoryesteem
json_metadata{"image":["https:\/\/steemitboard.com\/img\/notify.png"]}
created2019-06-13 09:55:51
last_update2019-06-13 09:55:51
depth1
children0
net_rshares0
last_payout2019-06-20 09:55:51
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length840
author_reputation38,705,954,145,809
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@curationkiwi ·
title
You got voted by @curationkiwi thanks to hughie8! This bot is managed by [KiwiJuce3](https://bit.ly/2HQOvIO) and run by [Rishi556](https://bit.ly/2OmBsQF), you can check both of them out there. To receive upvotes on your own posts, you need to join the [Kiwi Co. Discord](https://bit.ly/2U8Mo9M) and go to the room named #CurationKiwi. Submit your post there using the command  "!upvote (post link)" to receive upvotes on your post. CurationKiwi is currently supported by donations from users like you, so feel free to leave an upvote on our posts or comments to support us!
We have also recently added a new whitelist feature for those who would like to support CurationKiwi even more! If you would like to receive upvotes more than 2x greater than the normal upvote, all you need to do is delegate 50 SP to @CurationKiwi using [this link](https://app.steemconnect.com/sign/delegateVestingShares?account=curationkiwi&delegatee=curationkiwi&vesting_shares=99572.000000%20VESTS).
properties (22)
post_id76,333,342
authorcurationkiwi
permlinkre-leetcode-4-or-median-of-two-sorted-arrays
categoryesteem
json_metadata{"app":"Discord"}
created2019-06-13 16:28:15
last_update2019-06-13 16:28:15
depth1
children0
net_rshares0
last_payout2019-06-20 16:28:15
cashout_time1969-12-31 23:59:59
total_payout_value0.000 SBD
curator_payout_value0.000 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length978
author_reputation2,747,191,214,125
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
@steemexplorers ·
$0.04
title
You have been upvoted by all four members of the @steemexplorers team. Steemexplorers is an initiative to help bring all Steemians information on various services and communities operating all on the STEEM blockchain in a centralized location to save you time and help you grow here on Steemit. It's free, it's easy, and there's a whole lot of information here that you can put to good use. Please come by our discord channel to learn more and feel free to ask as many questions as you'd like. We're here to help! Link to Discord: https://discord.gg/6QrMCFq
👍  ,
properties (23)
post_id76,333,353
authorsteemexplorers
permlinkre-leetcode-4-or-median-of-two-sorted-arrays
categoryesteem
json_metadata{"app":"Discord"}
created2019-06-13 16:28:36
last_update2019-06-13 16:28:36
depth1
children0
net_rshares71,269,420,874
last_payout2019-06-20 16:28:36
cashout_time1969-12-31 23:59:59
total_payout_value0.032 SBD
curator_payout_value0.007 SBD
pending_payout_value0.000 SBD
promoted0.000 SBD
body_length557
author_reputation65,900,527,192,856
root_title"LeetCode 4 | Median of Two Sorted Arrays 寻找两个有序数组的中位数"
beneficiaries[]
max_accepted_payout1,000,000.000 SBD
percent_steem_dollars10,000
author_curate_reward""
vote details (2)
Help/Feedback