题目描述
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()方法排序， 取中间数即可。
/**
* @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解法
/**
* @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
};
运行结果
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
This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.
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.
You just received a 14.39% upvote from @honestbot, courtesy of @hughie8!
赞如果是买的就不好了。#esteem 有抽成10%
Posted using Partiko Android
(⊙o⊙)哦 我不知道哦，， 多谢告知、
我也是刚装了eSteem试试， 感觉界面好看
小买 都是minimum payment, 花的少， 主要为了reputation提的快
Thanks for using eSteem!
Your post has been voted as a part of eSteem encouragement program. Keep up the good work! Install Android, iOS Mobile app or Windows, Mac, Linux Surfer app, if you haven't already!
Learn more: https://esteem.app
Join our discord: https://discord.gg/8eHupPq
你好鸭，hughie8!
@cnbuddy给您叫了一份外卖！
由 @sasaadrian 一灯大师 迎着沙尘暴 跑着步 念着软哥金句:"别以为你长的稀有样我们就应该物以稀为贵。" 给您送来
大闸蟹
吃饱了吗？跟我猜拳吧！ 石头，剪刀，布～
如果您对我的服务满意，请不要吝啬您的点赞～
@onepagex
石头
You win!!!! 你赢了！ 给你1枚SHOP币！
Congratulations @hughie8! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPVote for @Steemitboard as a witness to get one more award and increased upvotes!
You got voted by @curationkiwi thanks to hughie8! This bot is managed by KiwiJuce3 and run by Rishi556, you can check both of them out there. To receive upvotes on your own posts, you need to join the Kiwi Co. Discord 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.