AlgoViz Lab交互式算法学习Algorithms first
寻找两个正序数组的中位数 · 交互式算法学习
在 O(log(m+n)) 时间内求两个升序数组中位数。
#4 · 二分查找
寻找两个正序数组的中位数
Median of Two Sorted Arrays
nums1 = [1,3], nums2 = [2]线性序列3 个关键状态
步骤 1较短数组是 [2]，尝试分割 i=0。
partition1
03
12
2推荐
二分较短数组分割线
时间
O(log min(m,n))空间 O(1)寻找分割，使左半最大值不大于右半最小值。
1function findMedianSortedArrays(a, b) {2 if (a.length > b.length) return findMedianSortedArrays(b, a);3 let l = 0,4 r = a.length,5 total = a.length + b.length;6 while (l <= r) {7 const i = (l + r) >> 1,8 j = Math.floor((total + 1) / 2) - i;9 const al = i ? a[i - 1] : -Infinity,10 ar = i < a.length ? a[i] : Infinity,11 bl = j ? b[j - 1] : -Infinity,12 br = j < b.length ? b[j] : Infinity;13 if (al <= br && bl <= ar) return total % 2 ? Math.max(al, bl) : (Math.max(al, bl) + Math.min(ar, br)) / 2;14 al > br ? r = i - 1 : l = i + 1;15 }16}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private int m;3 private int n;4 private int[] nums1;5 private int[] nums2;6 7 public double findMedianSortedArrays(int[] nums1, int[] nums2) {8 m = nums1.length;9 n = nums2.length;10 this.nums1 = nums1;11 this.nums2 = nums2;12 int a = f(0, 0, (m + n + 1) / 2);13 int b = f(0, 0, (m + n + 2) / 2);14 return (a + b) / 2.0;15 }16 17 private int f(int i, int j, int k) {18 if (i >= m) {19 return nums2[j + k - 1];20 }21 if (j >= n) {22 return nums1[i + k - 1];23 }24 if (k == 1) {25 return Math.min(nums1[i], nums2[j]);26 }27 int p = k / 2;28 int x = i + p - 1 < m ? nums1[i + p - 1] : 1 << 30;29 int y = j + p - 1 < n ? nums2[j + p - 1] : 1 << 30;30 return x < y ? f(i + p, j, k - p) : f(i, j + p, k - p);31 }32}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
寻找两个正序数组的中位数 · 解法对比
在 O(log(m+n)) 时间内求两个升序数组中位数。
- 测试用例
nums1 = [1,3], nums2 = [2]- 题目分类
- 二分查找
- 解法对比
- 2
归并到中间位置
双指针按序取数，只保留最近两个，走到中位数。
- 时间
O(m+n)- 空间
O(1)
二分较短数组分割线
寻找分割，使左半最大值不大于右半最小值。
- 时间
O(log min(m,n))- 空间
O(1)