分治算法用到极限是什么样子?

2019年9月13日16:18:01 发表评论 57 views

摆上题目:

分治算法用到极限是什么样子?

刚开始,看到时间复杂度为O(log(m+n)),立马就会想到二分法,没错,但是针对这一题而言,拿到的是两个数组,两个数组长度的和为奇数和偶数怎么处理?遇到什么情况进行二分?怎么分?这是我们必须考虑的问题。

一、什么是中位数?

首先,巩固一下中位数的概念: 有n个已经排好序的数。

  • 对于n为奇数的情况,中位数则是第(n+1)/2个,即最中间的那个数。
  • 对于n为偶数的情况,中位数则是第n/2个数和第n/2 + 1个数的算术平均值。

二、数组总长度奇数和偶数的情况怎么处理?

设总长度为n,找到第(n+1)/2个数,再找到第(n+2)/2个数 (注意:索引值都向下取整)。 然后,求两个数的平均值,即是最后要求的中位数。这样可以涵盖奇数和偶数的任一情况。

三、遇到什么情况进行二分?怎么分?

回到原题的起点,我们是要找到特定位置的数,那么想一想可以通过什么方式排除绝对不属于这个位置的数?

比如现在两个数组是[1, 2, 4, 6, 8], [5, 7, 9,11]。总长度为9,中位数为第5个,一个数组还好办,不过现在是两个数组的情况,我们采取一个比较巧妙的方式获得第5个数:

  • step1: 将5/2, 向下取整即为2,比较两个数组的第二个数,对应为2和7,明显前者比后者小,那么现在直接把第一个数组的前2个数剔除,因为它们百分之百在中位数的前面。
  • step2: 那么,现在我们确定了前2个数,那即将要求的就是后面所有的数字中排第3的数了。按照之前的做法,3/2,向下取整为1, 比较两个数组的第一个数,对应4和5, 前者比后者小,直接把第一个数组的前1个数剔除,因为百分之百在中位数的前面,不用考虑。
  • step3: OK,现在我们确定了前三个数,即将要求的就是后面所有的数字中排第2的数了,依照上述做法,我们剔除了5。
  • step4: 现在确定了前四个数,即将要求的就是后面所有的数字中第1个数了,直接比较目前两个数组的第一个数即可,6 < 7, 我们取6。完成!

将问题一般化就是获取第k个数,取两个数组中第k/2个数进行比较,如果比较小,就把这个数组的前k/2个元素全部剔除,依次循环,直到k为1或者有一个数组为空。

四、 如果k/2比其中一个数组的长度还要大怎么办?

这种情况,我们只需要取这个数组末尾的元素即可。

五、JS代码展示

代码如下:

//找到第k大的元素
const findKMax = (num1, start1, end1, num2, start2, end2, k) => {
    let len1 = end1 - start1 + 1;
    let len2 = end2 - start2 + 1;
    //这里我是来保证num1的长度一定小于num2,这样确定num1为空,直接来取num2的第k个数
    if (len1 > len2)
        return findKMax(num2, start2, end2, num1, start1, end1, k);
    if (len1 == 0) return num2[start2 + k - 1];

    if (k == 1) return Math.min(num1[start1], num2[start2]);
    // |0这个操作为向下取整
    //如果k/2比其中一个数组的长度还要大,取数组末尾元素即可
    let i = start1 + Math.min(len1, k / 2 | 0) - 1;
    let j = start2 + Math.min(len2, k / 2 | 0) - 1;

    if (num1[i] > num2[j])
        //已经剔除j - start2 + 1个元素
        return findKMax(num1, start1, end1, num2, j + 1, end2, k - (j - start2 + 1));
    else
        //已经剔除i - start1 + 1个元素
        return findKMax(num1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
}
//核心函数
const findMedianSortedArrays = (nums1, nums2) => {
    let m = nums1.length;
    let n = nums2.length;
    //向下取整
    let left = (m + n + 1) / 2 | 0;
    let right = (m + n + 2) / 2 | 0;
    
    //处理了数组总长度为奇数和偶数的情况
    return (findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, left) +
        findKMax(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1, right)) * 0.5;
}
复制代码

成功AC!

分治算法用到极限是什么样子?

作者:神三元
链接:https://juejin.im/post/5d7b051ef265da03925a7515
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: