#每日n题#两个正序数组的中位数
一个直观的方法
如果用“第k小数”的思想来做非常显而易见：找到 第「中位数位置」的小数。 使用双指针，哪一个数组当前的值小，就将对应指针向后移动一位。 但是这样需要不断遍历至中位数，复杂度为 O(m+n)O(m+n)O(m+n)
215. 数组中的第K个最大元素
【方法一】二分二分
本菜鸡二分法理解了很久……终于感觉找到了点思路 对于奇数偶数长度的处理，有一个比较tricky的方法：找到(m+n+12)\left(\frac{m + n + 1}{2}\right)(2m+n+1) 和 (m+n+22)\left(\frac{m + n + 2}{2}\right)(2m+n+2) 位置（向下取整）上的数字相加再 / 2。因为对于奇数，这两个值是相同的。 ps: 感觉这个方法也可以复用到其他类似的场景上
开始解题！ 首先，我们有两个数组A和B，分别取A[k2−1]A\left[\frac{k}{2}-1\right]A[2k−1]和B[k2−1]B\left[\frac{k}{2}-1\right]B[2k−1]的值。比较这俩的值，比如此时B[k2−1]B\left[\frac{k}{2}-1\right]B[2k−1] > A[k2−1]A\left[\frac{k}{2}-1\right]A[2k−1]，来分析一波： 注意我们现在关注的是两个数组的前(k2)\left(\frac{k}{2}\right)(2k)个值。因为他们加起来就是k，所以第k个数就只可能在他们中间产生。 B[k2−1]B\left[\frac{k}{2}-1\right]B[2k−1]此时是这k个数里面最大的（但是不能说它是整个合并数组里面第k大的，第 k 要么在 A 数组的后(k2)\left(\frac{k}{2}\right)(2k)个值，要么在 B 数组的前(k2)\left(\frac{k}{2}\right)(2k)个值），这样 A 数组的前(k2)\left(\frac{k}{2}\right)(2k)就可以丢掉了。 接下来就找两个数组的前(k4)\left(\frac{k}{4}\right)(4k)个值……递归，直到剩下第k个值。
这一块我一开始没很好理解，后面看了另外一个大佬题解就悟了(^o^)/
附上菜鸡题解（性能不是很好，待优化）
function result(arr, len1, len2){
return (arr[Math.floor((len1 + len2 + 1) / 2) - 1] + arr[Math.floor((len1 + len2 + 2) / 2) - 1]) / 2;
}
var findMedianSortedArrays = function(nums1, nums2) {
if(!nums1.length){ // 另一个数组为0
return result(nums2, 0, nums2.length);
}
if(!nums2.length){
return result(nums1, 0, nums1.length);
}
let isOdd = !!((nums1.length + nums2.length) % 2);
// target：划线左边的数的个数
let target = Math.ceil((nums1.length + nums2.length)/2);
// 防止下面找 i - 1 或 j - 1 的时候undefined
nums1[-1] = -1000000;
nums2[-1] = -1000000;
nums1.push(1000000);
nums2.push(1000000);
let i = Math.floor(target / 2);
let j = target - i;
// 保证最开始的指针都有值
while(nums1[i] === undefined){
i--;
j++;
}
while(nums2[j] === undefined){
i++;
j--;
}
// 主逻辑
while(nums1[i] !== undefined && nums2[j] !== undefined){
if (nums1[i] >= nums2[j - 1] && nums2[j] >= nums1[i - 1]){
return isOdd ? Math.max(nums2[j - 1], nums1[i - 1]) : (Math.max(nums2[j - 1], nums1[i - 1]) + Math.min(nums1[i], nums2[j])) / 2
}
if(nums1[i] < nums2[j - 1]){
i++;
j--;
}
if(nums2[j] < nums1[i - 1]){
i--;
j++;
}
}
if(!nums1[i]){
return isOdd ? nums2[target - 1] : (nums2[target - 1] + nums2[target]) / 2;
}
if(!nums2[j]){
return isOdd ? nums1[target - 1] : (nums1[target - 1] + nums1[target]) / 2;
}
}
ps：一直有个雷点，常踩常新——用while(nums1[i] && nums2[j])判空，会导致数组有值为0的时候出错。
【方法二】利用quicksort的partition
快排的本质就是不断给基数归位的过程，所以可以直接根据每一次被归位的数的位置，找到位于中位的数。
复习
之前一直不太理解快排，其实快排就是一个不断给元素“归位”的过程：只不过bubble sort是不断让大数冒泡归位，而快排是给当前的基准数（base）归位。为什么说基准数是归位的？当我们不断移动两端的指针、交换大于基准数和小于基准数的值，最终把基准数放到指针相遇的地方，就能保证base左边小于它，右边大于它，在数组有序时，它就只能待在那里。 当我们随机选定base时，还是一样，从两端向中心移动、选择、交换，再将base推到矛盾的中心。
let arr = [1, 3, 4, 2, 3];
// n1 和 n2 是即将交换的数的下标值
function swap(arr, n1, n2) {
let temp = arr[n1];
arr[n1] = arr[n2];
arr[n2] = temp;
}
function qs(arr, start, end) {
if (start >= end) {
return;
}
let i = start;
let j = end;
while (i < j) {
// 因为以最左边为基准值，所以先找小值
// 这么做是为了防止最左边的就是最小值，先找【大值】的话就会找到位列【第2】的值
// 最终变成【第1】和【第2】交换
// 从右往左找小值，遇到大值就继续走
while (i < j && arr[j] >= arr[start]) {
j--;
}
// 从左往右，遇到小值就继续走，【碰到另一个指针就停下】
while (i < j && arr[i] <= arr[start]) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
// 这里不需要多此一举i++或者j--
// 因为我们就是需要 i “碰上” j (i === j) 的这个位置
// 多此一举就会错位，使得元素交换出错
}
swap(arr, start, i);
qs(arr, start, i - 1);
qs(arr, i + 1, end);
}
qs(arr, 0, arr.length - 1); // [1, 2, 3, 3, 4]
在寻找第k位置上的元素时，我们只需要将k与base最终的位置进行比较，如果相等就皆大欢喜，但是如果k大于base，则说明我们只用在(base, end]这个区间寻找，反之，就去[start, base)不断找找找，总能找到的。 而在这道题找中位数的情境下，长度为偶数时，我们是需要找两个base数的，而且这两个base数被settled的时机未知，所以只能用一个对象 or 数组进行记录，等到两个都找到的时候再返回~
JS形参如何传递？
参数传递只有一种规则：按值传递，基于值的复制。原始类型复制的是值本身，所以这两份数据互不影响；引用类型复制的是引用值，所以形参和实参指向同一个对象，通过一个引用修改了对象，那么通过另外一个引用访问的对象就是修改后的对象。
swap函数应该这样写（我开始竟然企图将arr[n1]和arr[n2]作为参数……）：
let arr = [1,3,4,2,3]
// n1 和 n2 是即将交换的数的下标值
function swap(arr, n1, n2) {
let temp = arr[n1];
arr[n1] = arr[n2];
arr[n2] = temp;
}