P20. 求两个有序数组的中位数

https://algocasts.io/episodes/Qqpn6pkK

第k小这个思路还挺难理解的。
这个还挺好懂的:https://www.bilibili.com/video/av55991959?t=881

@muyiyangkang

嗯,这个小哥算法讲得不错。他的 Youtube 频道可以订阅一下。

在 findKthSmallestInSortedArrays 函数中的 while 循环内是怎么想到要判断 k == 1 的呢?

@singee

记住一个原则,所有的循环都是要穷尽终止条件的(递归也一样)。而终止条件一般依赖于循环或递归过程中,发生变化的变量(状态)。

findKthSmallestInSortedArrays 中使用了 while (true),于是我们要想的就是,怎样才能退出这个循环(正确的程序都是要在有限时间内停机的)。为此,我们要看这个循环里做的事情,使哪些变量(状态)发生了改变。在这个循环中,会被改变的变量有以下 5 个:

base1, base2, len1, len2, k

我们要做的就是看这 5 个变量达到什么状态时,就可以终止循环。这里面需要注意的是,base1 与 len1,base2 与 len2,事实上一体两面的东西。因为 base 加了多少,len 就会相应减去多少,具体可以看代码中以下这两条状态改变的语句:

        base1 += i;
        len1 -= i;
        ...
        base2 += j;
        len2 -= j;

因此,base 和 len 选一个来做终止条件即可。示例代码中使用了 len1 和 len2,也就是当其中一个长度减到 0 时,我们也就知道答案了,可以退出循环。事实上,你完全可以把它们换成 base1 和 base2,也就是,把刚进入循环时的语句改成如下代码:

    while (true) {
      if (base1 == nums1.length) return nums2[base2 + k - 1];
      if (base2 == nums2.length) return nums1[base1 + k - 1];
      ...
    }

这个非常好理解,len 减为 0 时,base 就达到数组长度。OK,说到这里,就剩下最后的主角 k 了。你问的是「怎么想到要判断 k == 1」。事实上,k 并没有更特别,它就是循环内发生了变化的其中一个变量。和 base 与 len 的分析一样,k 在循环内不断递减(k -= i;k -= j;),最终的一种可能是减到 k 的最小值 1(注意,第 k 小的 k 是从 1 开始的),于是 k == 1 也就自然成了终止条件之一。

那么 k 有没有可能绕过 1,直接被减成了 k <= 0 呢,这是不可能的。原因留给你自己去分析,提示可以看以下的代码:

      int i = Math.min(k / 2, len1);
      int j = Math.min(k - i, len2);
      ...
      if (i + j == k && a == b) return a;

小结一下就是,所有的循环都是要穷尽终止条件的(递归也一样)。而终止条件一般依赖于循环或递归过程中,发生变化的变量(状态)。大多数时候,循环的终止条件只由 1~2 个变量控制,因此一眼就知道什么时候跳出循环。但当发生改变的变量或状态比较多时,一个个列出来分析,就不会遗漏了。

Good Luck!