// nums = [[1, 3], [2]] // 1
nums = [[1, 2], [3]] // 1
// nums = [[1,2], [3,4]] // 1,2
// nums = [[1,2,5,6,7], [3,4]] // 3
findMedianSortedArrays(...nums)
expSearchGte([1, 2, 4.5, 5, 7], 0, 4)
function findMedianSortedArrays(nums1, nums2) {
debugger;
let totalLen = nums1.length + nums2.length;
// 找 mid，对于偶数个数字的情况，在头部补一个数字再找一次就行
let mid = Math.floor((totalLen - 1) / 2); // 3 -> 1,1; 4 -> 1,2
let arrs = [nums1, nums2];
let skipArr = [0, 0];
let pointer = nums1[0] <= nums2[0] ? 0 : 1; // pointer 指向更小的起始值数组
let loopCnt = 20; // 避免死循环
while (loopCnt-- >= 0) {
let skip = skipArr[pointer];
let arr = arrs[pointer];
let val = arr[skip];
let nextPointer = (pointer + 1) % 2;
let nextArr = arrs[nextPointer];
let nextArrSkip = skipArr[nextPointer];
// 找当前数组中比另一个数组的起始值更大的值
let nextSkip = expSearchGte(
arrs[pointer],
skipArr[pointer],
nextArr[nextArrSkip]
);
let nextSkipSafe = nextSkip === -1 ? arr.length - 1 : nextSkip;
// 1. 超出了 mid
if (mid < nextSkipSafe + nextArrSkip + 2) {
// mid + 1 = nextSkip + 1 + nextArrSkip + remain + 1
if (nextSkip === -1) {
// 中位数在当前数组，相当于去掉右边 nextArrSkip 个数，直接在当前数组找中位数
} else {
// 中位数在另一个数组
}
let remain =
mid - (nextSkip === -1 ? arr.length : nextSkip + 1) - nextArrSkip;
let r = nextArrSkip + remain < 0 ? arr[nextSkip === -1 ? arr.length + remain : ] : nextArr[nextArrSkip + remain];
return r;
}
// 2. 刚好是 mid，可直接算中位数，r 位于 gtEPos，l 位于 r 的上一个数或另一个数组的指针位置
if (mid === nextSkipSafe + nextArrSkip + 2) {
return arr[nextSkipSafe];
}
// 3. 没有超出 mid，继续循环
skipArr[pointer] = nextSkipSafe;
pointer = nextPointer;
}
return -1;
}
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.