题目链接
Generalize 的问题就是在两个 sorted 的 array 里找第k个大的数。我们假设 x <= k，我们取第一个 array 的第 x 个数，取第二个 array 的 第 k - x个数。如果：
- A[x] <= B[k - m] 那么 A 中前 x个数不可能是答案
- A[x] > B[k - m] 那么 B 中前 k - x个数不可能是答案
那么对于 x我们每次可以取 k / 2 和 A.length 中的较小值。当 k / 2 > A.length 时，我们会把A全部砍掉，但是这并不影响时间复杂度，因为当我们不需要考虑A时，直接return B的第k大的数就可以了。时间复杂度 O(log k) = O(log (m + n))，因为我们每次砍掉k的一半的数。代码如下：
第二种不好 generalize，每次我们砍掉较短的 array 的 (len - 1) / 2，的长度，对应的长的 array 我们也砍掉这么多，那么可以保证中位数还是砍掉后的两个 array 的中位数，这么一直做直到较短的 array 剩下 一个元素或者两个元素，即有两种base case，时间复杂度 O(log min (m , n))。代码如下：
No comments:
Post a Comment