求两个排序数组A和B的中位数
最优解 O(log (m+n))
不断删除个 k/2个数,然后 k = k/2
不断删掉数组中肯定不是第k小的那些数字,从而能够不断地减小数组,在这个过程中,我们要找的那个数字的序号(k)也会不断地减小。
数组中的哪些数字可以删除呢?
让我们假设k是4:
nums1: [a1, a2, a3, ...]
nums2: [b1, b2, b3, ...]
如果a2<b2,那么a2肯定可以删除。因为有可能比a2小的数字只有:
因此,a2最多只能是第3小的数字,肯定比我们要找的第4数字要小!从而a2,以及比a2还小的a1,都可以删除。
删除这两个数字以后,问题变成了:
nums1: [a3, ...]
nums2: [b1, b2, b3, ...]
从以上两个已排序数组中找出第2小的数字。(k已经变了,因为我们已经删除了两个比我们要找的那个数字还小的数字。)
同理,我们可以删除a3和b1中较小的那个数字,然后问题变成从剩余数字中找到第1小的数字。这个问题不就简单了吗?
原文来自微信。