网站动态图标,滁州住房与城乡建设官网,通州广州网站建设,建设论坛网站大全文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;寻找两个正序数组的中位数
出处#xff1a;4. 寻找两个正序数组的中位数
难度
8 级
题目描述
要求
给定两个大… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题寻找两个正序数组的中位数
出处4. 寻找两个正序数组的中位数
难度
8 级
题目描述
要求
给定两个大小分别为 m \texttt{m} m 和 n \texttt{n} n 的升序数组 nums1 \texttt{nums1} nums1 和 nums2 \texttt{nums2} nums2返回这两个升序数组的中位数。
要求时间复杂度是 O(log (m n)) \texttt{O(log (m n))} O(log (m n))。
示例
示例 1
输入 nums1 [1,3], nums2 [2] \texttt{nums1 [1,3], nums2 [2]} nums1 [1,3], nums2 [2] 输出 2.00000 \texttt{2.00000} 2.00000 解释合并数组是 [1,2,3] \texttt{[1,2,3]} [1,2,3]中位数是 2 \texttt{2} 2。
示例 2
输入 nums1 [1,2], nums2 [3,4] \texttt{nums1 [1,2], nums2 [3,4]} nums1 [1,2], nums2 [3,4] 输出 2.50000 \texttt{2.50000} 2.50000 解释合并数组是 [1,2,3,4] \texttt{[1,2,3,4]} [1,2,3,4]中位数是 2 3 2 2.5 \dfrac{\texttt{2} \texttt{3}}{\texttt{2}} \texttt{2.5} 2232.5。
数据范围 nums1.length m \texttt{nums1.length} \texttt{m} nums1.lengthm nums2.length n \texttt{nums2.length} \texttt{n} nums2.lengthn 0 ≤ m ≤ 1000 \texttt{0} \le \texttt{m} \le \texttt{1000} 0≤m≤1000 0 ≤ n ≤ 1000 \texttt{0} \le \texttt{n} \le \texttt{1000} 0≤n≤1000 1 ≤ m n ≤ 2000 \texttt{1} \le \texttt{m} \texttt{n} \le \texttt{2000} 1≤mn≤2000 -10 6 ≤ nums1[i], nums2[i] ≤ 10 6 \texttt{-10}^\texttt{6} \le \texttt{nums1[i], nums2[i]} \le \texttt{10}^\texttt{6} -106≤nums1[i], nums2[i]≤106
解法一
思路和算法
已知两个升序数组的长度分别是 m m m 和 n n n。计算两个升序数组的中位数可以转换成找到两个升序数组的所有元素中的第 k k k 小元素其中 0 ≤ k m n 0 \le k m n 0≤kmn。用 total m n \textit{total} m n totalmn 表示两个升序数组的长度之和。当 total \textit{total} total 是奇数时 k total − 1 2 k \dfrac{\textit{total} - 1}{2} k2total−1第 k k k 小元素即为中位数当 total \textit{total} total 是偶数时分别取 k total 2 − 1 k \dfrac{\textit{total}}{2} - 1 k2total−1 和 k total 2 k \dfrac{\textit{total}}{2} k2total两次第 k k k 小元素的平均数即为中位数。因此根据两个升序数组的长度之和是奇数或偶数执行一次或两次寻找第 k k k 小元素的操作即可得到中位数。
由于题目要求时间复杂度是 O ( log ( m n ) ) O(\log (m n)) O(log(mn))因此要求每次寻找第 k k k 小元素的操作的时间复杂度是 O ( log ( m n ) ) O(\log (m n)) O(log(mn))。需要使用二分查找实现。
用 k k k 表示目标值在剩余元素中的序号 k k k 从 0 0 0 开始序号为 k k k 表示剩余元素中有 k k k 个元素小于等于目标值用 index 1 \textit{index}_1 index1 和 index 2 \textit{index}_2 index2 分别表示数组 nums 1 \textit{nums}_1 nums1 和 nums 2 \textit{nums}_2 nums2 的首个剩余元素的下标初始时 index 1 \textit{index}_1 index1 和 index 2 \textit{index}_2 index2 都等于 0 0 0。剩余元素表示可能是目标值的元素查找过程中将不可能是目标值的元素排除。
每次查找时分别考虑两个数组的剩余元素中最小的 ⌈ k 2 ⌉ \Big\lceil \dfrac{k}{2} \Big\rceil ⌈2k⌉ 个元素共考虑 k 1 k 1 k1 个元素当 k k k 是奇数时或 k k k 个元素当 k k k 是偶数时这些元素在两个数组中的下标范围分别是 nums 1 \textit{nums}_1 nums1 的下标范围 [ index 1 , endIndex 1 ] [\textit{index}_1, \textit{endIndex}_1] [index1,endIndex1] 和 nums 2 \textit{nums}_2 nums2 的下标范围 [ index 2 , endIndex 2 ] [\textit{index}_2, \textit{endIndex}_2] [index2,endIndex2]其中 endIndex 1 index 1 ⌊ k − 1 2 ⌋ \textit{endIndex}_1 \textit{index}_1 \Big\lfloor \dfrac{k - 1}{2} \Big\rfloor endIndex1index1⌊2k−1⌋ endIndex 2 index 2 ⌊ k − 1 2 ⌋ \textit{endIndex}_2 \textit{index}_2 \Big\lfloor \dfrac{k - 1}{2} \Big\rfloor endIndex2index2⌊2k−1⌋。考虑 nums 1 [ endIndex 1 ] \textit{nums}_1[\textit{endIndex}_1] nums1[endIndex1] 和 nums 2 [ endIndex 2 ] \textit{nums}_2[\textit{endIndex}_2] nums2[endIndex2]其中的较大值是第 k k k 小元素当 k k k 是奇数时或第 k − 1 k - 1 k−1 小元素当 k k k 是偶数时因此其中的较小值一定不是第 k k k 小元素。对于较小值所在的数组可以将较小值以及较小值前面的元素全部排除。
需要注意的是 endIndex 1 \textit{endIndex}_1 endIndex1 和 endIndex 2 \textit{endIndex}_2 endIndex2 不能超出数组下标范围。如果一个数组的剩余元素个数少于 ⌈ k 2 ⌉ \Big\lceil \dfrac{k}{2} \Big\rceil ⌈2k⌉则该数组中考虑的元素是该数组中的全部剩余元素。因此有 endIndex 1 min ( index 1 ⌊ k − 1 2 ⌋ , m − 1 ) \textit{endIndex}_1 \min(\textit{index}_1 \Big\lfloor \dfrac{k - 1}{2} \Big\rfloor, m - 1) endIndex1min(index1⌊2k−1⌋,m−1) endIndex 2 min ( index 2 ⌊ k − 1 2 ⌋ , n − 1 ) \textit{endIndex}_2 \min(\textit{index}_2 \Big\lfloor \dfrac{k - 1}{2} \Big\rfloor, n - 1) endIndex2min(index2⌊2k−1⌋,n−1)。
由此可以根据三种情况分别做相应的处理缩小查找范围。 如果 nums 1 [ endIndex 1 ] nums 2 [ endIndex 2 ] \textit{nums}_1[\textit{endIndex}_1] \textit{nums}_2[\textit{endIndex}_2] nums1[endIndex1]nums2[endIndex2]则将 nums 1 \textit{nums}_1 nums1 的下标范围 [ index 1 , endIndex 1 ] [\textit{index}_1, \textit{endIndex}_1] [index1,endIndex1] 中的元素全部排除排除的元素个数是 endIndex 1 − index 1 1 \textit{endIndex}_1 - \textit{index}_1 1 endIndex1−index11。 如果 nums 1 [ endIndex 1 ] nums 2 [ endIndex 2 ] \textit{nums}_1[\textit{endIndex}_1] \textit{nums}_2[\textit{endIndex}_2] nums1[endIndex1]nums2[endIndex2]则将 nums 2 \textit{nums}_2 nums2 的下标范围 [ index 2 , endIndex 2 ] [\textit{index}_2, \textit{endIndex}_2] [index2,endIndex2] 中的元素全部排除排除的元素个数是 endIndex 2 − index 2 1 \textit{endIndex}_2 - \textit{index}_2 1 endIndex2−index21。 如果 nums 1 [ endIndex 1 ] nums 2 [ endIndex 2 ] \textit{nums}_1[\textit{endIndex}_1] \textit{nums}_2[\textit{endIndex}_2] nums1[endIndex1]nums2[endIndex2]则处理方式和 nums 1 [ endIndex 1 ] nums 2 [ endIndex 2 ] \textit{nums}_1[\textit{endIndex}_1] \textit{nums}_2[\textit{endIndex}_2] nums1[endIndex1]nums2[endIndex2] 相同。
每次查找之后将 k k k 的值减去排除的元素个数并将排除元素的数组的相应下标更新为该数组首个剩余元素的下标具体做法如下如果排除的是 nums 1 \textit{nums}_1 nums1 中的元素则将 index 1 \textit{index}_1 index1 更新为 endIndex 1 1 \textit{endIndex}_1 1 endIndex11如果排除的是 nums 2 \textit{nums}_2 nums2 中的元素则将 index 2 \textit{index}_2 index2 更新为 endIndex 2 1 \textit{endIndex}_2 1 endIndex21。
二分查找的条件是 index 1 m \textit{index}_1 m index1m index 2 n \textit{index}_2 n index2n 和 k 0 k 0 k0。如果三个条件之一不满足则二分查找结束得到目标值。 如果 index 1 m \textit{index}_1 m index1m则剩余元素都在 nums 2 \textit{nums}_2 nums2 中目标值是 nums 2 [ index 2 k ] \textit{nums}_2[\textit{index}_2 k] nums2[index2k]。 如果 index 2 n \textit{index}_2 n index2n则剩余元素都在 nums 1 \textit{nums}_1 nums1 中目标值是 nums 1 [ index 1 k ] \textit{nums}_1[\textit{index}_1 k] nums1[index1k]。 如果 k 0 k 0 k0则剩余元素中的最小元素是目标值目标值是 min ( nums 1 [ index 1 ] , nums 2 [ index 2 ] ) \min(\textit{nums}_1[\textit{index}_1], \textit{nums}_2[\textit{index}_2]) min(nums1[index1],nums2[index2])。
以下用一个例子说明该解法。
两个数组是 nums 1 [ 1 , 2 , 3 , 4 , 5 ] \textit{nums}_1 [1, 2, 3, 4, 5] nums1[1,2,3,4,5] nums 2 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] \textit{nums}_2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] nums2[1,2,3,4,5,6,7,8,9,10]两个数组的长度分别是 m 5 m 5 m5 n 10 n 10 n10长度之和是 15 15 15 k 7 k 7 k7。初始时 index 1 0 \textit{index}_1 0 index10 index 2 0 \textit{index}_2 0 index20。 根据 index 1 0 \textit{index}_1 0 index10 index 2 0 \textit{index}_2 0 index20 和 k 7 k 7 k7 计算得到 endIndex 1 3 \textit{endIndex}_1 3 endIndex13 endIndex 2 3 \textit{endIndex}_2 3 endIndex23。由于 nums 1 [ 3 ] nums 2 [ 3 ] \textit{nums}_1[3] \textit{nums}_2[3] nums1[3]nums2[3]因此将 nums 1 \textit{nums}_1 nums1 的下标范围 [ 0 , 3 ] [0, 3] [0,3] 排除排除 4 4 4 个元素更新得到 k 3 k 3 k3 index 1 4 \textit{index}_1 4 index14。 根据 index 1 4 \textit{index}_1 4 index14 index 2 0 \textit{index}_2 0 index20 和 k 3 k 3 k3 计算得到 endIndex 1 4 \textit{endIndex}_1 4 endIndex14 endIndex 2 1 \textit{endIndex}_2 1 endIndex21。由于 nums 1 [ 4 ] nums 2 [ 1 ] \textit{nums}_1[4] \textit{nums}_2[1] nums1[4]nums2[1]因此将 nums 2 \textit{nums}_2 nums2 的下标范围 [ 0 , 1 ] [0, 1] [0,1] 排除排除 2 2 2 个元素更新得到 k 1 k 1 k1 index 2 2 \textit{index}_2 2 index22。 根据 index 1 4 \textit{index}_1 4 index14 index 2 2 \textit{index}_2 2 index22 和 k 1 k 1 k1 计算得到 endIndex 1 4 \textit{endIndex}_1 4 endIndex14 endIndex 2 2 \textit{endIndex}_2 2 endIndex22。由于 nums 1 [ 4 ] nums 2 [ 2 ] \textit{nums}_1[4] \textit{nums}_2[2] nums1[4]nums2[2]因此将 nums 2 \textit{nums}_2 nums2 的下标范围 [ 2 , 2 ] [2, 2] [2,2] 排除排除 1 1 1 个元素更新得到 k 0 k 0 k0 index 2 3 \textit{index}_2 3 index23。 此时 k 0 k 0 k0二分查找结束 nums 1 [ 4 ] \textit{nums}_1[4] nums1[4] 和 nums 2 [ 3 ] \textit{nums}_2[3] nums2[3] 中的较小值 4 4 4 即为目标值。
代码
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int m nums1.length, n nums2.length;int total m n;if (total % 2 1) {int medianIndex (total - 1) / 2;return findKthSmallest(medianIndex, nums1, nums2);} else {int medianIndex1 total / 2 - 1, medianIndex2 total / 2;return (findKthSmallest(medianIndex1, nums1, nums2) findKthSmallest(medianIndex2, nums1, nums2)) / 2.0;}}public int findKthSmallest(int k, int[] nums1, int[] nums2) {int m nums1.length, n nums2.length;int index1 0, index2 0;while (index1 m index2 n k 0) {int endIndex1 Math.min(index1 (k - 1) / 2, m - 1);int endIndex2 Math.min(index2 (k - 1) / 2, n - 1);int num1 nums1[endIndex1], num2 nums2[endIndex2];if (num1 num2) {k - endIndex1 - index1 1;index1 endIndex1 1;} else {k - endIndex2 - index2 1;index2 endIndex2 1;}}if (index1 m) {return nums2[index2 k];} else if (index2 n) {return nums1[index1 k];} else {return Math.min(nums1[index1], nums2[index2]);}}
}复杂度分析 时间复杂度 O ( log ( m n ) ) O(\log (m n)) O(log(mn))其中 m m m 和 n n n 分别是数组 nums 1 \textit{nums}_1 nums1 和 nums 2 \textit{nums}_2 nums2 的长度。每次寻找第 k k k 小元素时 k k k 的初始值是 m n m n mn 的一半附近的整数每次查找将 k k k 的值减小一半因此时间复杂度是 O ( log ( m n ) ) O(\log (m n)) O(log(mn))。 空间复杂度 O ( 1 ) O(1) O(1)。
解法二
思路和算法
解法一的时间复杂度是 O ( log ( m n ) ) O(\log (m n)) O(log(mn))该时间复杂度已经很低但是这道题还存在时间复杂度更低的解法。
为了找到中位数需要在数组 nums 1 \textit{nums}_1 nums1 和 nums 2 \textit{nums}_2 nums2 中分别找到分割点 cut 1 \textit{cut}_1 cut1 和 cut 2 \textit{cut}_2 cut2将每个数组分割成两个部分。 数组 nums 1 \textit{nums}_1 nums1 被分割成下标范围 [ 0 , cut 1 − 1 ] [0, \textit{cut}_1 - 1] [0,cut1−1] 和下标范围 [ cut 1 , m − 1 ] [\textit{cut}_1, m - 1] [cut1,m−1] 两部分左边部分的长度是 cut 1 \textit{cut}_1 cut1。 数组 nums 2 \textit{nums}_2 nums2 被分割成下标范围 [ 0 , cut 2 − 1 ] [0, \textit{cut}_2 - 1] [0,cut2−1] 和下标范围 [ cut 2 , n − 1 ] [\textit{cut}_2, n - 1] [cut2,n−1] 两部分左边部分的长度是 cut 2 \textit{cut}_2 cut2。
其中 0 ≤ cut 1 ≤ m 0 \le \textit{cut}_1 \le m 0≤cut1≤m 0 ≤ cut 2 ≤ n 0 \le \textit{cut}_2 \le n 0≤cut2≤n即每个数组分割成的两个部分中可以有一个部分为空。
假设 nums 1 [ − 1 ] nums 2 [ − 1 ] − ∞ \textit{nums}_1[-1] \textit{nums}_2[-1] -\infty nums1[−1]nums2[−1]−∞ nums 1 [ m ] nums 2 [ n ] ∞ \textit{nums}_1[m] \textit{nums}_2[n] \infty nums1[m]nums2[n]∞分割应满足以下两个条件。 两个数组的左边部分的最大值小于等于两个数组的右边部分的最小值 max ( nums 1 [ cut 1 − 1 ] , nums 2 [ cut 2 − 1 ] ) ≤ min ( nums 1 [ cut 1 ] , nums 2 [ cut 2 ] ) \max(\textit{nums}_1[\textit{cut}_1 - 1], \textit{nums}_2[\textit{cut}_2 - 1]) \le \min(\textit{nums}_1[\textit{cut}_1], \textit{nums}_2[\textit{cut}_2]) max(nums1[cut1−1],nums2[cut2−1])≤min(nums1[cut1],nums2[cut2])。 两个数组的左边部分的长度之和为两个数组的长度之和的一半向上取整 cut 1 cut 2 ⌈ m n 2 ⌉ \textit{cut}_1 \textit{cut}_2 \Big\lceil \dfrac{m n}{2} \Big\rceil cut1cut2⌈2mn⌉。
将两个数组的左边部分统称为前半部分将两个数组的右边部分统称为后半部分则前半部分的最大值小于等于后半部分的最小值前半部分的元素个数为两个数组的长度之和的一半向上取整。
用 total m n \textit{total} m n totalmn 表示两个升序数组的长度之和用 lowerSize ⌈ total 2 ⌉ \textit{lowerSize} \Big\lceil \dfrac{\textit{total}}{2} \Big\rceil lowerSize⌈2total⌉ 表示前半部分的元素个数。当 total \textit{total} total 是奇数时中位数是前半部分的最大值当 total \textit{total} total 是偶数时中位数是前半部分的最大值与后半部分的最小值的平均数。
由于已知 cut 1 cut 2 lowerSize \textit{cut}_1 \textit{cut}_2 \textit{lowerSize} cut1cut2lowerSize因此可以在 nums 1 \textit{nums}_1 nums1 中寻找 cut 1 \textit{cut}_1 cut1当 cut 1 \textit{cut}_1 cut1 确定之后 cut 2 \textit{cut}_2 cut2 也可以确定。
寻找 cut 1 \textit{cut}_1 cut1 可以使用二分查找实现。由于两个数组都是升序数组 nums 1 [ cut 1 − 1 ] ≤ nums 1 [ cut 1 ] \textit{nums}_1[\textit{cut}_1 - 1] \le \textit{nums}_1[\textit{cut}_1] nums1[cut1−1]≤nums1[cut1] 和 nums 2 [ cut 2 − 1 ] ≤ nums 2 [ cut 2 ] \textit{nums}_2[\textit{cut}_2 - 1] \le \textit{nums}_2[\textit{cut}_2] nums2[cut2−1]≤nums2[cut2] 都满足因此只需要满足 nums 1 [ cut 1 − 1 ] ≤ nums 2 [ cut 2 ] \textit{nums}_1[\textit{cut}_1 - 1] \le \textit{nums}_2[\textit{cut}_2] nums1[cut1−1]≤nums2[cut2] 和 nums 2 [ cut 2 − 1 ] ≤ nums 1 [ cut 1 ] \textit{nums}_2[\textit{cut}_2 - 1] \le \textit{nums}_1[\textit{cut}_1] nums2[cut2−1]≤nums1[cut1] 即可。二分查找需要查找满足 nums 1 [ cut 1 − 1 ] ≤ nums 2 [ cut 2 ] \textit{nums}_1[\textit{cut}_1 - 1] \le \textit{nums}_2[\textit{cut}_2] nums1[cut1−1]≤nums2[cut2] 的最大下标 cut 1 \textit{cut}_1 cut1。
用 low \textit{low} low 和 high \textit{high} high 分别表示二分查找的下标范围的下界和上界初始时 low 0 \textit{low} 0 low0 high m \textit{high} m highm。每次查找时取 index 1 \textit{index}_1 index1 为 low \textit{low} low 和 high \textit{high} high 的平均数向上取整并得到 index 2 lowerSize − index 1 \textit{index}_2 \textit{lowerSize} - \textit{index}_1 index2lowerSize−index1比较 nums 1 [ index 1 − 1 ] \textit{nums}_1[\textit{index}_1 - 1] nums1[index1−1] 和 nums 2 [ index 2 ] \textit{nums}_2[\textit{index}_2] nums2[index2] 的大小关系调整查找的下标范围。 如果 nums 1 [ index 1 − 1 ] ≤ nums 2 [ index 2 ] \textit{nums}_1[\textit{index}_1 - 1] \le \textit{nums}_2[\textit{index}_2] nums1[index1−1]≤nums2[index2]则 cut 1 ≥ index 1 \textit{cut}_1 \ge \textit{index}_1 cut1≥index1因此在下标范围 [ index 1 , high ] [\textit{index}_1, \textit{high}] [index1,high] 中继续查找。 如果 nums 1 [ index 1 − 1 ] nums 2 [ index 2 ] \textit{nums}_1[\textit{index}_1 - 1] \textit{nums}_2[\textit{index}_2] nums1[index1−1]nums2[index2]则 cut 1 index 1 \textit{cut}_1 \textit{index}_1 cut1index1因此在下标范围 [ low , index 1 − 1 ] [\textit{low}, \textit{index}_1 - 1] [low,index1−1] 中继续查找。
当 low high \textit{low} \textit{high} lowhigh 时查找结束此时 low \textit{low} low 即为 cut 1 \textit{cut}_1 cut1。
得到 cut 1 \textit{cut}_1 cut1 之后即可得到 cut 2 \textit{cut}_2 cut2 nums 1 [ cut 1 − 1 ] \textit{nums}_1[\textit{cut}_1 - 1] nums1[cut1−1] 和 nums 2 [ cut 2 − 1 ] \textit{nums}_2[\textit{cut}_2 - 1] nums2[cut2−1] 中的最大值是前半部分的最大值 nums 1 [ cut 1 ] \textit{nums}_1[\textit{cut}_1] nums1[cut1] 和 nums 2 [ cut 2 ] \textit{nums}_2[\textit{cut}_2] nums2[cut2] 中的最小值是后半部分的最小值。根据前半部分的最大值和后半部分的最小值即可计算中位数。 当 total \textit{total} total 是奇数时中位数是前半部分的最大值。 当 total \textit{total} total 是偶数时中位数是前半部分的最大值与后半部分的最小值的平均数。
该解法的时间复杂度是 O ( log m ) O(\log m) O(logm)优于解法一的 O ( log ( m n ) ) O(\log (m n)) O(log(mn))。
实现方面由于只需要在一个数组中二分查找因此可以选择较短的数组二分查找时间复杂度是 O ( log min ( m , n ) ) O(\log \min(m, n)) O(logmin(m,n))。
以下用一个例子说明上述过程。
两个数组是 nums 1 [ 1 , 2 , 3 , 4 , 5 ] \textit{nums}_1 [1, 2, 3, 4, 5] nums1[1,2,3,4,5] nums 2 [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ] \textit{nums}_2 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] nums2[1,2,3,4,5,6,7,8,9,10]两个数组的长度分别是 m 5 m 5 m5 n 10 n 10 n10长度之和是 15 15 15前半部分的元素个数是 8 8 8。初始时 low 0 \textit{low} 0 low0 high 5 \textit{high} 5 high5。 根据 low 0 \textit{low} 0 low0 和 high 5 \textit{high} 5 high5 计算得到 index 1 3 \textit{index}_1 3 index13 index 2 5 \textit{index}_2 5 index25。由于 nums 1 [ 2 ] ≤ nums 2 [ 5 ] \textit{nums}_1[2] \le \textit{nums}_2[5] nums1[2]≤nums2[5]因此将 low \textit{low} low 更新为 3 3 3。 根据 low 3 \textit{low} 3 low3 和 high 5 \textit{high} 5 high5 计算得到 index 1 4 \textit{index}_1 4 index14 index 2 4 \textit{index}_2 4 index24。由于 nums 1 [ 3 ] ≤ nums 2 [ 4 ] \textit{nums}_1[3] \le \textit{nums}_2[4] nums1[3]≤nums2[4]因此将 low \textit{low} low 更新为 4 4 4。 根据 low 4 \textit{low} 4 low4 和 high 5 \textit{high} 5 high5 计算得到 index 1 5 \textit{index}_1 5 index15 index 2 3 \textit{index}_2 3 index23。由于 nums 1 [ 4 ] nums 2 [ 3 ] \textit{nums}_1[4] \textit{nums}_2[3] nums1[4]nums2[3]因此将 high \textit{high} high 更新为 4 4 4。 此时 low high \textit{low} \textit{high} lowhigh二分查找结束。根据 low 4 \textit{low} 4 low4 计算得到 cut 1 4 \textit{cut}_1 4 cut14 cut 2 4 \textit{cut}_2 4 cut24前半部分的最大值是 4 4 4后半部分的最小值是 5 5 5。由于两个数组的长度之和是奇数因此中位数是前半部分的最大值中位数是 4 4 4。
代码
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {return nums1.length nums2.length ? findMedian(nums1, nums2) : findMedian(nums2, nums1);}public double findMedian(int[] shorter, int[] longer) {int length1 shorter.length, length2 longer.length;int total length1 length2;int lowerSize (total 1) / 2;int low 0, high length1;while (low high) {int index1 low (high - low 1) / 2;int index2 lowerSize - index1;int left1 shorter[index1 - 1];int right2 longer[index2];if (left1 right2) {low index1;} else {high index1 - 1;}}int cut1 low, cut2 lowerSize - low;int lower1 cut1 0 ? Integer.MIN_VALUE : shorter[cut1 - 1];int lower2 cut2 0 ? Integer.MIN_VALUE : longer[cut2 - 1];int higher1 cut1 length1 ? Integer.MAX_VALUE : shorter[cut1];int higher2 cut2 length2 ? Integer.MAX_VALUE : longer[cut2];int lowerMax Math.max(lower1, lower2), higherMin Math.min(higher1, higher2);if (total % 2 1) {return lowerMax;} else {return (lowerMax higherMin) / 2.0;}}
}复杂度分析 时间复杂度 O ( log min ( m , n ) ) O(\log \min(m, n)) O(logmin(m,n))其中 m m m 和 n n n 分别是数组 nums 1 \textit{nums}_1 nums1 和 nums 2 \textit{nums}_2 nums2 的长度。在较短的数组中二分查找范围是 [ 0 , min ( m , n ) ] [0, \min(m, n)] [0,min(m,n)]二分查找的次数是 O ( log min ( m , n ) ) O(\log \min(m, n)) O(logmin(m,n))每次查找的时间是 O ( 1 ) O(1) O(1)因此时间复杂度是 O ( log min ( m , n ) ) O(\log \min(m, n)) O(logmin(m,n))。 空间复杂度 O ( 1 ) O(1) O(1)。
