Leetcode4 Median of Two Sorted Arrays

LeetCode第4题,求两个数组nums1nums2的中位数,要求对数复杂度。这个思路很清晰,就是二分。一开始想的lower_bound比较一波,算一下偏移,然后两段去掉相同数目的元素,构成一个子问题。不过实现的时候被字符串常见的边界情况和上下中位数困住了,想了好久,后来发现其实自己想复杂了,这就是一个求第k个数的问题,直接二分答案就好了。

nums1[m1]nums2[m2]为两个数列nums1[0..n1-1]nums2[0..n2-1]的中位数(长度为奇数)和上中位数(长度为偶数),显然当nums1[m1] = nums2[m2]时为一个结束条件,此时按照奇偶长度判断一下即可。
nums1[m1] < nums2[m2]时,显然m2取大了,m1取小了,此时中位数应该位于nums1[m1..n1-1]nums2[0..m2]里面,注意中位数仍然可能取m2的,例如nums1 = [1, 2, 3, 4]nums2 = [1, 3, 4]的情况,同理中位数也仍然可能取m1。但是如果单独拿出这两个片段来更新,仍然得不到子问题,因为中位数虽然在这两个片段内,但是这两个片段的中位数并不一定等于原数组的中位数。因此产生了两种想法:第一种做法试图去掉相等数量的最小值和最大值,形成依然“对称”的数组;另一种做法是不追求切完的数列依然对称,而是直接记录去掉了多少个最小值,因而新的数列中还需要去掉多少个最小值,实际上转化为求第k个小数的问题。

对于第一种方法。假定nums1[m1] < nums2[m2],令j = lower_bound(nums2, nums2 + n2, nums1[m1]),其中lower_bound二分搜索可以使用python中的bisect.bisect_left代替,显然j < m1,所以如果按照(m1, j)来分割,则小端变少了m2 - j个,因此nums2的分割点应该位于[j + 1, m2 - 1]这个区间内。同理,令i = upper_bound(nums1, nums1 + n1, nums2[n2])nums1分割点应该在[m1 + 1, i - 1]这个区间内。
一个比较简单的想法是,分别对于两个数列直接去掉min(n1, n2) / 2个元素,这样是为了保证两个数组都有足够的元素可以取。此外要注意min(n1, n2) / 2 == 0的情况程序会陷入无限递归的情况,这是由于某一个数组的长度为1导致的,所以预先判定下数组长度为1的情况,写下来代码是这样的
但是这样会WA,Leetcode可以直接告诉你哪一个点WA了,于是发现对于数据[1, 4], [2, 3]是不正确的。其实这个程序每次去掉的未必是最小的数,因为最小的数未必在中位数小的数列中。

对于第二种方法,这里选择直接二分值而不是下标。对每个二分出来的值,再在两个数组中找到它的插入位置ij,并比较i + jk的大小,如果大了,说明中位数取大了,取左区间继续二分。
附上代码
这里注意两点,第一是lower_bound(nums1, nums1 + len, mid)始终返回是nums1mid上确界的下标,如果mid大于nums1中所有数,下标是nums1.end(),直接取值会造成nums1越界,例如[1, 2], [3, 4]的情况。出现这种情况是因为mid取小了,而nums1整体小于nums2lower_boundnums1末尾借用了一个数导致下标越界。第二是两个数列中都没有mid这个数,当i + j == k时,取到的是两个数组对mid的上确界,如[1, 1, 3, 3], [1, 1, 3, 3]中第一轮取k = 4, i = 2, j = 2, mid = 2 < nums1[i] = nums2[j] = 3