#每日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;
}