4.寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2： 输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
提示： nums1.length == m nums2.length == n 0 <= m <= 1000 0 <= n <= 1000 1 <= m + n <= 2000 -106 <= nums1[i], nums2[i] <= 106
方法
暴力法（时间复杂度不符合要求）
var findMedianSortedArrays = function(nums1, nums2) {let x = nums1.concat(nums2);let y = x.sort((a,b)=>a-b); // 把数组按照正序排序let z = x.length;// 判断数组长度奇还是偶if(z%2!=0){ // 奇数返回t = y[(z-1)/2];}else{t = (y[z/2]+y[(z-2)/2])/2; // 偶数处理 截取中间的俩个数字}return t;};
复杂度分析
-
二分查找
⭐️方法1
思路
数组合并之后在排序的复杂度是O((m+n) log(m+n))不符合题意，题目要求的是O(log (m+n))，我们一看到logn的复杂度就联想到了二分。二分长度较小的数组，找到这个数组二分的位置，在根据这个二分的位置和两个数组的总长度找到另一个数组二分的位置，比较这两个位置的四个数是否满足交叉小于等于，不满足继续二分，满足就找到了解
算法
复杂度分析 时间复杂度：O(log( min(m，n)) )，m、n分别是nums1和nums2的长度。每次二分循环的长度都会少一半，只要二分比较短的数组即可。
空间复杂度：O(1) ```javascript /**
- @param {number[]} nums1
- @param {number[]} nums2
@return {number} */ var findMedianSortedArrays = function (nums1, nums2) { let A = nums1; let B = nums2; let m = A.length; let n = B.length; if (m > n) { return findMedianSortedArrays(B, A); // 保证 m <= n } let iMin = 0, iMax = m; while (iMin <= iMax) { // let i = Math.floor((iMin + iMax) / 2); // let j = Math.floor((m + n + 1) / 2) - i; let i = (iMin + iMax) >> 1; let j = ((m + n + 1) >> 1) - i; if (j != 0 && i != m && B[j - 1] > A[i]) { // i 需要增大 iMin = i + 1; } else if (i != 0 && j != n && A[i - 1] > B[j]) { // i 需要减小 iMax = i - 1; } else { // 达到要求，并且将边界条件列出来单独考虑 let maxLeft = 0; if (i == 0) {
maxLeft = B[j - 1];
} else if (j == 0) {
maxLeft = A[i - 1];
} else {
maxLeft = Math.max(A[i - 1], B[j - 1]);
} // if ((m + n) % 2 == 1) { if ((m + n) & 1 === 1) { // 奇数
return maxLeft;
} // 奇数的话不需要考虑右半部分
let minRight = 0; if (i == m) {
minRight = B[j];
} else if (j == n) {
minRight = A[i];
} else {
minRight = Math.min(B[j], A[i]);
} return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果。要的是带小数的结果，所以不能>>1 } } return 0.0; };
<a name="yiyJs"></a>### 方法2：第k小数**思路**<br />[第k小数的思路参考](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/di-k-xiao-shu-jie-fa-ni-zhen-de-dong-ma-by-geek-8m/)<br />要证明：使用第k小数折半剔除的方法，可以保证每次剔除的数都在第k小数的左边。<br />已知条件：有两个有序数组，元素总个数n。<br />我们挑选第一次删除作为演示，至于后续的删除，都是一样的。<br />只要证：只需要证明4的右边存在的元素个数 >= n - k + 1<br />n - (k / 2 * 2 -1) >= n - k + 1<br />证明：<br />n - (k / 2 * 2 -1) >= n - k + 1<br />k - k / 2 * 2 >= 0<br />k >= k / 2 * 2<br />当k为偶数时，k >= k<br />当k为奇数时，k >= k -1<a name="FjoqN"></a>## ⭐️⭐️划分数组在统计中，中位数被用来：> 将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。1、首先，在任意位置 i 将 \text{A}A 划分成两个部分：```javascriptleft_A | right_AA[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
由于A 中有 m 个元素， 所以有 m+1种划分的方法（i∈[0,m]）。
len(left_A)=i,len(right_A)=m−i. 注意：当 i = 0i=0 时，left_A 为空集， 而当 i = mi=m 时, right_A 为空集。
（1）采用同样的方式，在任意位置 j将 B 划分成两个部分：
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
2、将left_A 和 left_B 放入一个集合，并将 right_A 和right_B 放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part：
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
3、（1）当A 和 B 的总长度是偶数时，如果可以确认：
- len(left_part) = len(right_part)
- max(left_part) ≤ min(right_part)
那么，{A,B} 中的所有元素已经被划分为相同长度的两个部分，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值：
（2）当 A 和 B 的总长度是奇数时，如果可以确认：
- len(left_part) = len(right_part)+1
- max(left_part) ≤ min(right_part)
那么，{A,B} 中的所有元素已经被划分为两个部分，前一部分比后一部分多一个元素，且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值：
median = max(left_part)
4、第一个条件对于总长度是偶数和奇数的情况有所不同，但是可以将两种情况合并。第二个条件对于总长度是偶数和奇数的情况是一样的。
要确保这两个条件，只需要保证：
- i + j = m - i + n - j（当 m+n 为偶数）或 i + j = m - i + n - j + 1（当 m+n 为奇数）。等号左侧为前一部分的元素个数，等号右侧为后一部分的元素个数。将 i 和 j 全部移到等号左侧，我们就可以得到
。这里的分数结果只保留整数部分。 - 0≤i≤m，0≤j≤n。如果我们规定 A 的长度小于等于 B 的长度，即 m≤n。这样对于任意的i∈[0,m]，都有
，那么我们在 [0, m]的范围内枚举 i并得到 j，就不需要额外的性质了。- 如果 A 的长度较大，那么我们只要交换 A 和 B 即可。
- 如果 m > n，那么得出的 j 有可能是负数。
- B[j−1] ≤ A[i] 以及 A[i−1] ≤ B[j]，即前一部分的最大值小于等于后一部分的最小值。
5、为了简化分析，假设 A[i−1], B[j−1], A[i], B[j] 总是存在。对于i=0、i=m、j=0、j=n 这样的临界条件，我们只需要规定A[−1]=B[−1]=−∞，A[m]=B[n]=∞ 即可。这也是比较直观的：当一个数组不出现在前一部分时，对应的值为负无穷，就不会对前一部分的最大值产生影响；当一个数组不出现在后一部分时，对应的值为正无穷，就不会对后一部分的最小值产生影响。
6、所以我们需要做的是：
在 [0, m]中找到 i，使得： B[j−1] ≤ A[i] 且A[i−1] ≤ B[j]，其中
我们证明它等价于：
在 [0, m]中找到最大的 i，使得： A[i−1] ≤ B[j]，其中
这是因为：
- 当 i从 0∼m 递增时，A[i−1] 递增，B[j] 递减，所以一定存在一个最大的 i满足A[i−1]≤B[j]；
- 如果 i 是最大的，那么说明 i+1 不满足。将 i+1带入可以得到 A[i]>B[j−1]，也就是 B[j−1]<A[i]，就和我们进行等价变换前 i的性质一致了（甚至还要更强）。
因此我们可以对 i 在 [0,m] 的区间上进行二分搜索，找到最大的满足 A[i−1]≤B[j] 的 i 值，就得到了划分的方法。此时，划分前一部分元素中的最大值，以及划分后一部分元素中的最小值，才可能作为就是这两个数组的中位数。
算法
var findMedianSortedArrays = (nums1, nums2) => {
let len1 = nums1.length, len2 = nums2.length
if (len1 > len2) return findMedianSortedArrays(nums2, nums1)//对nums1和nums2中长度较小的二分
let len = len1 + len2//总长
let start = 0, end = len1 //进行二分的开始和结束位置
let partLen1, partLen2
while (start <= end) {
partLen1 = (start + end) >> 1; // nums1二分的位置
partLen2 = ((len + 1) >> 1) - partLen1; // nums2二分的位置
//L1:nums1二分之后左边的位置，L2，nums1二分之后右边的位置
//R1:nums2二分之后左边的位置，R2，nums2二分之后右边的位置
//如果左边没字符了，就定义成-Infinity，让所有数都大于它，否则就是nums1二分的位置左边一个
let L1 = partLen1 === 0 ? -Infinity : nums1[partLen1 - 1]
//如果左边没字符了，就定义成-Infinity，让所有数都大于它，否则就是nums2二分的位置左边一个
let L2 = partLen2 === 0 ? -Infinity : nums2[partLen2 - 1]
//如果右边没字符了，就定义成Infinity，让所有数都小于它，否则就是nums1二分的位置
let R1 = partLen1 === len1 ? Infinity : nums1[partLen1]
//如果右边没字符了，就定义成Infinity，让所有数都小于它，否则就是nums1二分的位置
let R2 = partLen2 === len2 ? Infinity : nums2[partLen2]
if (L1 > R2) {//不符合交叉小于等于 继续二分
end = partLen1 - 1
} else if (L2 > R1) {//不符合交叉小于等于 继续二分
start = partLen1 + 1
} else { // L1 <= R2 && L2 <= R1 符合交叉小于等于
return len % 2 === 0 ?
(Math.max(L1, L2) + Math.min(R1, R2)) / 2 : //长度为偶数返回作左侧较大者和右边较小者和的一半
Math.max(L1, L2) //长度为奇数返回作左侧较大者
}
}
}
复杂度分析
- 时间复杂度：我们对较短的数组进行了二分查找，所以时间复杂度是O(logmin(m,n)))。查找的区间是 [0, m]，而该区间的长度在每次循环之后都会减少为原来的一半。所以，只需要执行 logm 次循环。由于每次循环中的操作次数是常数，所以时间复杂度为 O(\log m)O(logm)。由于我们可能需要交换nums1和 nums2 使得 m≤n，因此时间复杂度是 O(logmin(m,n)))。
- 空间复杂度：只有一些固定的变量，和数组长度无关，所以空间复杂度是 O(1)。
若有收获，就点个赞吧
0 人点赞
