js寻找两个数组的差集_leetcode4.寻找两个正序数组的中位数

leetcode4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序&＃xff08;从小到大&＃xff09;数组 nums1 和 nums2。

请你找出这两个正序数组的中位数&＃xff0c;并且要求算法的时间复杂度为 O(log(m &＃43; n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

示例 2:

方法一&＃xff1a;暴力法

思路&＃xff1a;

首先考虑最简单的暴力法&＃xff0c;没想到居然通过了。

直接将两个数组合并&＃xff0c;排序&＃xff0c;然后根据长度返回中位数即可。

排序可以写归并排序&＃xff0c;这里直接调用sort函数了。

代码&＃xff1a;

结果&＃xff1a;

方法二&＃xff1a;二分查找递归

思路&＃xff1a;

上面的时间复杂度不符合要求&＃xff0c;这个要求的复杂度需要采用二分法。我们可以把这个问题转换为找两个数组中第k小的数&＃xff0c;那么找中位数&＃xff0c;根据总长度的奇偶&＃xff0c;就是调用这个函数一次&＃xff0c;或者两次来取平均的过程。

总体的思路是&＃xff0c;我们首先判断是否有一个数组是空&＃xff0c;如果是的话&＃xff0c;那么很简单&＃xff0c;只是对另一个数组找中位数即可&＃xff1b;若不是&＃xff0c;再进行下面过程&＃xff0c;判断总长度奇偶。如果总长度为奇数&＃xff0c;只要找到最中间的那个元素&＃xff0c;即可&＃xff0c;设为第k小的数&＃xff1b;若为偶数&＃xff0c;则找到中间两个数&＃xff0c;第k小和第k&＃43;1小&＃xff0c;再取平均即可。

下面介绍如何找到第k小的数&＃xff0c;我们使用二分法&＃xff0c;上下数组分别取第numm&＃61;k//2个数&＃xff0c;进行对比&＃xff0c;若nums1[numm] <&＃61; nums2[numm]&＃xff0c;则说明nums1的前面这numm个数肯定小于目标数&＃xff0c;抛弃&＃xff0c;反之抛弃nums2的前面numm个数&＃xff1b;下面问题就转换为在调整完&＃xff08;抛弃掉没用的数&＃xff09;之后的两个数组中&＃xff0c;找第k-numm小的数的问题&＃xff0c;就可以继续递归了。简单流程如下图所示。

此时numm&＃61;&＃61;2&＃xff0c;两个数组的第二个元素&＃xff0c;nums1的比较大&＃xff0c;那么nums2的前numm个元素就抛弃掉&＃xff0c;如下图黄色部分抛弃掉&＃xff0c;然后问题就转换为剩下两个数组中找第2小的数。

问题转换为如图示问题。

由于2 <5&＃xff0c;把nums1的前numm个元素删除掉&＃xff0c;即把2删除掉&＃xff0c;那么问题转换为。

由于此时就是找最小的数&＃xff0c;不需要再二分&＃xff0c;直接返回两个数组比较小的第一个数即可。这也是我们递归的一种边界条件&＃xff0c;为了节约空间&＃xff0c;我们不将数组传入递归函数&＃xff0c;不对数组进行改变&＃xff0c;只使用left1、right1、left2、right2表示nums1和nums2的搜索范围&＃xff0c;t表示找第t的数。那么我们的递归终止条件有&＃xff1a;

• 其中一个数组的left大于right了&＃xff0c;说明这个数组在上一层已经全部被抛弃了&＃xff08;上一层在调整边界时&＃xff0c;左边界要加上抛弃的长度&＃xff0c;全部抛弃的时候&＃xff0c;得到的新的左边界&＃xff0c;刚好超过右边界。&＃xff09;&＃xff0c;只要返回另一个数组的第t小数即可&＃xff0c;即nums[left&＃43;t-1]。
• 两个数组都还有数&＃xff0c;t&＃61;&＃61;1&＃xff0c;只要比较两个数组第一个元素&＃xff0c;返回小的即可。

这里面还有一个小小的问题&＃xff0c;我们在计算numm的时候&＃xff0c;如果数组剩余的长度right-left&＃43;1不足numm时候&＃xff0c;我们就直接使用right的数来进行判断&＃xff0c;因此表示参与抛弃的长度的时候&＃xff0c;我们需要与现存数组长度进行判断&＃xff0c;取小的。length1 &＃61; min(numm,right1-left1&＃43;1) 、length2 &＃61; min(numm,right2-left2&＃43;1)。

代码&＃xff1a;

结果&＃xff1a;